#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 2137
#endif

const int N = 100100;
const ll INF64 = 2e18;
int n, m;
vector<pair<int, int>> adj[N];
vector<pair<int, int>> dag[N];
int dp[N];
bool vis[N];

vector<ll> go(int s) {
  vector<ll> dst(n, INF64);
  priority_queue<pair<ll, int>> q;
  dst[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    ll d = -q.top().first;
    int u = q.top().second;
    q.pop();
    if (d != dst[u]) {
      continue;
    }
    for (auto [v, w] : adj[u]) {
      if (d + w < dst[v]) {
        dst[v] = d + w;
        q.push({-dst[v], v});
      }
    }
  }
  return dst;
}

void dfs(int u, int x) {
  dp[u] = 0;
  for (auto [v, w] : dag[u]) {
    if (dp[v] == -1) {
      dfs(v, x);
    }
    dp[u] = max(dp[u], dp[v] + (w == x));
  }
}

void cut(int u, int x) {
  vis[u] = true;
  for (int i = 0; i < ssize(dag[u]); i++) {
    auto [v, w] = dag[u][i];
    if (dp[v] + (w == x) == dp[u]) {
      if (!vis[v]) {
        cut(v, x);
      }
    } else {
      swap(dag[u][i], dag[u].back());
      dag[u].pop_back();
      i--;
    }
  }
}

void solve() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    adj[i].clear();
    dag[i].clear();
  }
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--; v--;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  auto ds = go(0);
  auto dt = go(n - 1);
  vector<int> ww;
  for (int i = 0; i < n; i++) {
    for (auto [j, w] : adj[i]) {
      if (ds[i] + w + dt[j] == ds[n - 1]) {
        dag[i].push_back({j, w});
        ww.push_back(w);
      }
    }
  }
  sort(ww.begin(), ww.end(), greater<int>());
  ww.resize(unique(ww.begin(), ww.end()) - ww.begin());
  for (int w : ww) {
    for (int i = 0; i < n; i++) {
      dp[i] = -1;
      vis[i] = false;
    }
    dfs(0, w);
    cut(0, w);
  }
  vector<int> ans;
  ans.push_back(0);
  while (ans.back() != n - 1) {
    ans.push_back(dag[ans.back()][0].first);
  }
  cout << ssize(ans) << '\n';
  for (int u : ans) {
    cout << u + 1 << " \n"[u == ans.back()];
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}