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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define subnb true
#define Lnb true
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int N = (int)1e5 + 50;
const ll INF = (ll)1e18;

struct edge {
    int to, cost;
};

int n, m;
vector<edge> G[N];
ll dis[N], dp[N];
vector<edge> og[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    while(T--) {
        cin >> n >> m;
        rep(i, 0, n) G[i].clear(), og[i].clear();
        rep(i, 0, m) {
            int u, v, w; cin >> u >> v >> w; u--, v--;
            G[u].push_back({v, w});
            G[v].push_back({u, w});
        }
        fill(dis, dis + n, INF);
        priority_queue<pll, vector<pll>, greater<>> pque;
        pque.push({0, 0});
        dis[0] = 0;
        while(!pque.empty()) {
            auto p = pque.top(); pque.pop();
            ll d = p.first, v = p.second;
            if(dis[v] != d) continue;
            for (auto &e : G[v]) {
                if(d + e.cost < dis[e.to]) {
                    dis[e.to] = d + e.cost;
                    pque.push({dis[e.to], e.to});
                }
            }
        }
        rep(i, 0, n) {
            for (auto e: G[i]) {
                if(dis[i] == dis[e.to] + e.cost) {
                    og[i].push_back({e.to, e.cost});
                }
            }
        }
        vi ord(n);
        iota(all(ord), 0);
        sort(all(ord), [&](const int i, const int j) {
            return dis[i] < dis[j];
        });
//        for (int x : ord) cout << x << ": " << dis[x] << endl;
        function<ll(int)> count_max = [&](int lim) {
//            cout << "lim: " << lim << endl;
            for (int i : ord) {
                dp[i] = -1;
                for (auto e : og[i]) {
                    dp[i] = max({dp[i], dp[e.to], 1LL * (e.cost < lim ? e.cost : -1)});
                }
            }
            ll v = dp[n - 1];
            if(v == -1) return -1LL;
            for (int i : ord) {
                dp[i] = 0;
                for (auto e : og[i]) dp[i] = max(dp[i], dp[e.to] + (e.cost == v));
            }
            for (int i : ord) {
                vector<edge> ng;
                for (auto e : og[i]) {
                    if(dp[i] == dp[e.to] + (e.cost == v)) ng.push_back(e);
                }
                og[i] = ng;
            }
            return v;
        };
        int cur = 50005;
        while(cur != -1) {
            cur = count_max(cur);
        }
        vi res;
        cur = n - 1;
        while(cur != 0) {
//            cout << cur << endl;
            res.push_back(cur);
            cur = og[cur][0].to;
        }
        res.push_back(0);
        reverse(all(res));
        cout << sz(res) << '\n';
        for (int x : res) cout << x + 1 << " ";
        cout << '\n';


    }


    
}