#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

using ll = long long;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, ll>>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    vector<pair<ll, int>> dist(n, {1e18, 1e9});
    set<pair<pair<ll, int>, int>> st;
    dist[n - 1] = {0, 1};
    st.emplace(dist[n - 1], n - 1);
    while (st.size()) {
        int u = st.begin()->second;
        st.erase(st.begin());
        for (auto [to, w] : g[u]) {
            pair<ll, int> pp = {dist[u].first + w, dist[u].second + 1};
            if (dist[to] > pp) {
                st.erase({dist[to], to});
                dist[to] = pp;
                st.emplace(dist[to], to);
            }
        }
    }
    vector<int> ans = {0};
    for (int u = 0; u != n - 1; ) {
        int v = n;
        for (auto [to, w] : g[u]) {
            pair<ll, int> pp = {dist[u].first - w, dist[u].second - 1};
            if (dist[to] == pp) v = min(v, to);
        }
        ans.push_back(v);
        u = v;
    }
    cout << ans.size() << '\n';
    for (auto to : ans) cout << to + 1 << ' ';
    cout << '\n';
}

int main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#else
    freopen("input.txt", "r", stdin);
#endif
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}