#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());
//        cout << u << ' ' << dist[u].first << ' ' << dist[u].second << endl;
        for (auto [to, w] : g[u]) {
            pair<ll, int> pp = {dist[u].first + w, dist[u].second + 1};
//            cout << u << ' ' << to << ' ' << pp.first << ' ' << pp.second << endl;
            if (dist[to] > pp) {
                st.erase({dist[to], to});
                dist[to] = pp;
                st.emplace(dist[to], to);
            }
        }
    }
//    for (auto [x, y] : dist) {
//        cout << x << ' ' << y << endl;
//    }
//    cout << 111 << endl;
    vector<int> ans = {0};
    for (int u = 0; u != n - 1; ) {
//        cout << u << endl;
        pair<int, int> qq = {-1, -n};
//        cout << u << ' ' << qq.first << ' ' << qq.second << ' ' << dist[u].first << ' ' << dist[u].second << endl;
        for (auto [to, w] : g[u]) {
//            cout << to << ' ' << dist[to].first << ' ' << dist[to].second << endl;
            pair<ll, int> pp = {dist[u].first - w, dist[u].second - 1};
            if (dist[to] == pp) {
//                cout << w << ' ' << to << endl;
                qq = max(qq, {w, -to});
            }
        }
//        cout << u << ' ' << qq.first << ' ' << qq.second << endl;
        int v = -qq.second;
        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;
}