#include <bits/stdc++.h>
using namespace std;
const char el = '\n';
typedef long long ll;
const int inf = 1e9;
struct edge {
  int u, v, w;
};
// struct graph {
//   vector<vector<pair<int, int>>> e;
//   graph(int n) : e(n + 1) {}
//   void adde(int u, int v, int w) {
//     e[u].push_back({v, w});
//     e[v].push_back({u, w});
//   }
//   void rev
// };
vector<edge> rev(vector<edge> ed) {
  for (auto &[u, v, w] : ed) swap(u, v);
  return ed;
}
vector<ll> dijk(int s, int n, const vector<edge> &ed) {
  vector<vector<pair<int, int>>> e(n + 1);
  for (auto [u, v, w] : ed) e[u].push_back({v, w});
  vector<ll> dis(n + 1, inf);
  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 greater<pair<int, int>>>
      que;
  que.push({dis[s] = 0, s});
  while (que.size()) {
    auto [d, u] = que.top();
    que.pop();
    if (d > dis[u]) continue;
    for (auto [v, w] : e[u])
      if (dis[v] > dis[u] + w) que.push({dis[v] = dis[u] + w, v});
  }
  return dis;
}
vector<int> bfs(int s, int n, const vector<edge> &ed, int cur) {
  vector<vector<pair<int, int>>> e(n + 1);
  for (auto [u, v, w] : ed) e[u].push_back({v, w != cur});
  vector<int> dis(n + 1, inf);
  deque<pair<int, int>> que;
  que.push_back({dis[s] = 0, s});
  while (que.size()) {
    auto [d, u] = que.front();
    que.pop_front();
    if (d > dis[u]) continue;
    for (auto [v, w] : e[u])
      if (dis[v] > dis[u] + w) {
        if (w)
          que.push_back({dis[v] = dis[u] + w, v});
        else
          que.push_front({dis[v] = dis[u] + w, v});
      }
  }
  return dis;
}
int maxw(vector<edge> &ed, int cur) {
  int res = 0;
  for (auto &[u, v, w] : ed)
    if (w < cur) res = max(res, w);
  return res;
}
vector<edge> filt1(vector<ll> ds, vector<ll> dt, vector<edge> ed, int dis) {
  vector<edge> res;
  for (auto [u, v, w] : ed)
    if (ds[u] + dt[v] + w == dis) res.push_back({u, v, w});
  return res;
}
vector<edge> filt2(vector<int> ds, vector<int> dt, vector<edge> ed, int cur,
                   int dis) {
  vector<edge> res;
  for (auto [u, v, w] : ed)
    if (ds[u] + dt[v] + (w != cur) == dis) res.push_back({u, v, w});
  return res;
}
vector<int> path(int s, int t, int n, vector<edge> ed) {
  vector<int> res;
  vector<int> to(n + 1);
  for (auto [u, v, w] : ed) to[u] = v;
  while (s != t) {
    res.push_back(s);
    s = to[s];
  }
  res.push_back(t);
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(15);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, m;
    cin >> n >> m;
    vector<edge> ed(m);
    for (auto &[u, v, w] : ed) cin >> u >> v >> w;
    auto rv = rev(ed);
    ed.insert(ed.end(), rv.begin(), rv.end());
    auto dis1 = dijk(1, n, ed), disn = dijk(n, n, rev(ed));
    ed = filt1(dis1, disn, ed, dis1[n]);
    int cur = inf;
    while (cur = maxw(ed, cur)) {
      auto dis1 = bfs(1, n, ed, cur), disn = bfs(n, n, rev(ed), cur);
      ed = filt2(dis1, disn, ed, cur, dis1[n]);
    }
    auto p = path(1, n, n, ed);
    cout << p.size() << el;
    for (auto v : p) cout << v << ' ';
    cout << el;
  }
  return 0;
}