#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int MM = 1e5+5,inf = 0x3f3f3f3f;
int n,m; int d1[MM],dn[MM],ti; vector<pair<int,int>> adj[MM],g[MM],rg[MM];
bitset<MM> good,vis; vector<int> ans,cur;
bool rec(int u){
    if(u == n){
        cur.push_back(n);
        ans = cur;
        return true;
    }
    if(vis[u]) return false;
    cur.push_back(u);
    vis[u] = 1;
    for(auto[v,t] : g[u]){
        if(good[t] && rec(v)) return true;
    }
    cur.pop_back();
    return false;
}
void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        d1[i] = dn[i] = inf;
        g[i].clear(); rg[i].clear();
        adj[i].clear();
    }
    ti = 0;
    vis.reset(); good.reset();
    ans.clear(); cur.clear();
    vector<array<int,3>> el(m);
    for(int i = 0; i < m; i++){
        int u,v,w; cin >> u >> v >> w;
        el[i] = {u,v,w};
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    auto go = [&](int st, int dist[]){
        dist[st] = 0; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> q;
        q.push({0,st});
        while(q.size()){
            auto[d,u] = q.top(); q.pop();
            for(auto[v,w] : adj[u]) if(dist[v] > dist[u]+w){
                dist[v] = dist[u]+w;
                q.push({dist[v],v});
            }
        }
    };
    go(1,d1); go(n,dn);
    int tot = d1[n]; 
    unordered_map<int,vector<array<int,3>>> mp;
    vector<array<int,3>> rel;
    for(auto[u,v,w]:el){
        if(dn[v]+d1[u]+w == tot){
            mp[w].push_back({u,v,++ti});
            g[u].push_back({v,ti}); rg[v].push_back({u,ti}); 
            rel.push_back({u,v,ti});
            //cout << u << " " << v << " " << w << "\n";
        }
        swap(u,v);
        if(dn[v]+d1[u]+w == tot){
            mp[w].push_back({u,v,++ti});
            g[u].push_back({v,ti}); rg[v].push_back({u,ti}); 
            rel.push_back({u,v,ti});
            //cout << u << " " << v << " " << w << "\n";
        }
    }
    for(int i = 1; i <= ti; i++) good[i] = 1;
    for(int i = tot; i >= 1; i--){
        if(!mp.count(i)) continue;
        auto& vec = mp[i]; bitset<MM> cur,cur_good;
        // push low
        queue<int> q; bool fl = 0;
        for(auto[u,v,t] : vec){
            if(!good[t]) continue;
            q.push(v); cur[v] = 1; fl = 1;
            cur_good[t] = 1;
        }
        if(!fl) continue;
        while(q.size()){
            int u = q.front(); q.pop();
            for(auto[v,t] : g[u]) if(!cur[v] && good[t]){
                cur[v] = 1;
                q.push(v); 
            }
        }
        for(auto[u,v,t] : rel){
            if(!good[t]) continue;
            if(cur[v] && cur[u]) cur_good[t] = 1;
        }
        cur.reset();
        for(auto[u,v,t] : vec){
            if(!good[t]) continue;
            q.push(u); cur[u] = 1;
        }
        while(q.size()){
            int u = q.front(); q.pop();
            for(auto[v,t] : rg[u]) if(!cur[v] && good[t]){
                cur[v] = 1;
                q.push(v);
            }
        }
        for(auto[u,v,t] : rel){
            if(!good[t]) continue;
            if(cur[v] && cur[u]) cur_good[t] = 1;
        }
        /*
        cout << "for " << i << "\n";
        for(int i = 1; i <= ti; i++) cout << cur_good[i];
        cout << "\n";*/
        good &= cur_good;
    }  
    // generate
    /*
    for(int i = 1; i <= ti; i++) cout << good[i];
    cout << "\n";*/
    bool res = rec(1); assert(res);
    cout << ans.size() << "\n";
    for(int i = 0; i < (int)ans.size(); i++) cout << ans[i] << " \n"[i==(int)ans.size()-1];
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t; while(t--) solve();
}
// min length will be <= 5e4, so only sqrt distinct weights that are useful