#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


constexpr Int INF = 1001001001001001001LL;

int N, M;
vector<int> A, B;
vector<Int> C;

vector<vector<int>> G;
vector<Int> dist;

int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d%d", &N, &M);
    A.resize(2 * M);
    B.resize(2 * M);
    C.resize(2 * M);
    for (int i = 0; i < M; ++i) {
      scanf("%d%d%lld", &A[i], &B[i], &C[i]);
      --A[i];
      --B[i];
      A[M + i] = B[i];
      B[M + i] = A[i];
      C[M + i] = C[i];
    }
    M *= 2;
    
    G.assign(N, {});
    for (int i = 0; i < M; ++i) {
      G[A[i]].push_back(i);
    }
    
    using Entry = pair<Int, int>;
    priority_queue<Entry, vector<Entry>, greater<Entry>> que;
    dist.assign(N, INF);
    que.emplace(dist[0] = 0, 0);
    vector<int> us;
    for (; !que.empty(); ) {
      const Int c = que.top().first;
      const int u = que.top().second;
      que.pop();
      if (c == dist[u]) {
        us.push_back(u);
        for (const int i : G[u]) {
          const Int cc = c + C[i];
          const int v = A[i] ^ B[i] ^ u;
          if (chmin(dist[v], cc)) {
            que.emplace(cc, v);
          }
        }
      }
    }
// cerr<<"dist = "<<dist<<endl;
// cerr<<"us = "<<us<<endl;
    assert((int)us.size() == N);
    assert(dist[N - 1] <= 50'000);
    
    vector<int> del(M, 0);
    for (int i = 0; i < M; ++i) {
      if (dist[A[i]] + C[i] != dist[B[i]]) {
        del[i] = 1;
      }
    }
    
    // (max, num)
    vector<pair<Int, int>> dp(N);
    vector<int> prv(N);
    for (Int thr = dist[N - 1] + 1; ; ) {
      fill(dp.begin(), dp.end(), make_pair(-1, 0));
      fill(prv.begin(), prv.end(), -1);
      dp[0] = make_pair(0, 0);
      for (const int u : us) {
        for (const int i : G[u]) if (!del[i]) {
          const Int c = (C[i] < thr) ? C[i] : -1;
          const Int mx = max(dp[u].first, c);
          int num = 0;
          if (mx == dp[u].first) num += dp[u].second;
          if (mx == c) num += 1;
          const int v = B[i];
          if (chmax(dp[v], make_pair(mx, num))) {
            prv[v] = u;
          }
        }
      }
      if (dp[N - 1].second == 0) {
        break;
      }
      for (const int u : us) {
        for (const int i : G[u]) if (!del[i]) {
          const Int c = (C[i] < thr) ? C[i] : -1;
          const Int mx = max(dp[u].first, c);
          int num = 0;
          if (mx == dp[u].first) num += dp[u].second;
          if (mx == c) num += 1;
          const int v = B[i];
          if (dp[v] != make_pair(mx, num)) {
            del[i] = 1;
          }
        }
      }
      thr = dp[N - 1].first;
    }
    
    vector<int> ans;
    for (int u = N - 1; ; ) {
      ans.push_back(u);
      if (u == 0) break;
      u = prv[u];
    }
    reverse(ans.begin(), ans.end());
    printf("%d\n", (int)ans.size());
    for (int h = 0; h < (int)ans.size(); ++h) {
      if (h) printf(" ");
      printf("%d", ans[h] + 1);
    }
    puts("");
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}