#include <bits/stdc++.h>
using namespace std;
template <class T> struct LinkedListWeightedGraph {
  vector<int> HEAD, TO, NXT; vector<T> WEIGHT;
  LinkedListWeightedGraph(int V = 0) : HEAD(V, -1) {}
  void reserveDiEdges(int maxEdges) {
    TO.reserve(maxEdges); NXT.reserve(maxEdges); WEIGHT.reserve(maxEdges);
  }
  void addDiEdge(int from, int to, T weight) {
    NXT.push_back(HEAD[from]); HEAD[from] = int(TO.size());
    TO.push_back(to); WEIGHT.push_back(weight);
  }
  void addBiEdge(int v, int w, T weight) {
    addDiEdge(v, w, weight); addDiEdge(w, v, weight);
  }
  struct Iterator {
    const LinkedListWeightedGraph &G; int i;
    Iterator(const LinkedListWeightedGraph &G, int i) : G(G), i(i) {}
    Iterator &operator ++ () { i = G.NXT[i]; return *this; }
    pair<int, T> operator * () const {
      return make_pair(G.TO[i], G.WEIGHT[i]);
    }
    bool operator != (const Iterator &it) const { return i != it.i; }
  };
  struct Adj {
    const LinkedListWeightedGraph &G; int v;
    Adj(const LinkedListWeightedGraph &G, int v) : G(G), v(v) {}
    const Iterator begin() const { return Iterator(G, G.HEAD[v]); }
    const Iterator end() const { return Iterator(G, -1); }
  };
  const Adj operator [] (int v) const { return Adj(*this, v); }
  int size() const { return HEAD.size(); }
  void free(){
    vector<int>().swap(HEAD); 
    vector<int>().swap(TO); 
    vector<int>().swap(NXT); 
    vector<T>().swap(WEIGHT);
  }
};
const int MM = 1e5+5; const int64_t inf = 0x3f3f3f3f3f3f3f3f;
using Gr = LinkedListWeightedGraph<int>;
int n,m; int64_t d1[MM],dn[MM]; int ti; Gr adj,g,rg;

bitset<MM> good,vis; vector<int> ans,cur;
bool rec(int u){
    if(u == n-1){
        cur.push_back(n-1);
        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;
}
array<int,4> rel[MM*3];
void solve(){
    cin >> n >> m;
    adj = Gr(n); g = Gr(n); rg = Gr(n);
    for(int i = 0; i < n; i++){
        d1[i] = dn[i] = inf;
    }
    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; u--; v--;
        el[i] = {u,v,w};
        adj.addDiEdge(u,v,w);
        adj.addDiEdge(v,u,w);
    }
    auto go = [&](int st, int64_t dist[]){
        dist[st] = 0; priority_queue<pair<int64_t,int>,vector<pair<int64_t,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(0,d1); go(n-1,dn);
    int tot = d1[n-1]; //assert(tot <= 5e4);
    // don't need anymore
    adj.free();
    for(auto[u,v,w]:el){
        if(dn[v]+d1[u]+w == tot){
            g.addDiEdge(u,v,ti); rg.addDiEdge(v,u,ti);
            rel[ti] = {w,u,v,ti}; 
            ti++;
            //cout << u << " " << v << " " << w << "\n";
        }
        swap(u,v);
        if(dn[v]+d1[u]+w == tot){
            g.addDiEdge(u,v,ti); rg.addDiEdge(v,u,ti);
            rel[ti] = {w,u,v,ti}; 
            ti++;
            //cout << u << " " << v << " " << w << "\n";
        }
    }
    for(int i = 0; i < ti; i++) good[i] = 1;
    sort(rel,rel+ti,greater<>());
    vector<int> vals;
    for(int i = 0; i < ti; i++){
        int j = i;
        while(j+1 < ti && rel[j+1][0] == rel[i][0]) j++;
        bool fl = 0; bitset<MM> we;
        for(int k = i; k <= j; k++){
            auto[w,u,v,t] = rel[k];
            if(good[t]){
                fl = 1;
                we[t] = 1;
            }
        }
        if(!fl){
            i = j;
            continue;
        }
        bitset<MM> cur_good;
        // go dag dp
        auto amog = [&](int st, Gr gr){
            vector<int> dp(n),ind(n);
            for(int i = 0; i < n; i++){
                for(auto[v,t] : gr[i]){
                    if(!good[t]) continue;
                    ind[v]++;
                }
            }
            queue<int> q;
            for(int i = 0; i < n; i++){
                if(ind[i] == 0){
                    q.push(i); 
                }
            }
            while(q.size()){
                int u = q.front(); q.pop();
                for(auto[v,t] : gr[u]) if(good[t]){
                    dp[v] = max(dp[v],dp[u]+we[t]);
                    if(--ind[v] == 0){
                        q.push(v);
                    }
                }
            }
            vector<int>().swap(ind);
            return dp;
        };
        auto g1 = amog(0,g), gn = amog(n-1,rg);
        int targ = g1[n-1];
        for(int k = 0; k < ti; k++){
            auto[w,u,v,t] = rel[k];
            if(!good[t]) continue;
            if(g1[u]+we[t]+gn[v] == targ){
                cur_good[t] = 1;
            }
        }
        vector<int>().swap(g1);
        vector<int>().swap(gn);
        good &= cur_good;
        i = j;
    }
    /*
    for(int i = tot; i >= 1; i--){
        if(!mp.count(i)) continue;
        auto& vec = mp[i];
        bool fl = 0; bitset<MM> we;
        for(auto[u,v,t]:vec) if(good[t]){
            fl = 1; we[t] = 1;
        }
        if(!fl) continue;
        bitset<MM> cur_good;
        // go dag dp
        auto amog = [&](int st, Gr gr){
            vector<int> dp(n+1),ind(n+1);
            for(int i = 1; i <= n; i++){
                for(auto[v,t] : gr[i]){
                    if(!good[t]) continue;
                    ind[v]++;
                }
            }
            queue<int> q;
            for(int i = 1; i <= n; i++){
                if(ind[i] == 0){
                    q.push(i); 
                }
            }
            while(q.size()){
                int u = q.front(); q.pop();
                for(auto[v,t] : gr[u]) if(good[t]){
                    dp[v] = max(dp[v],dp[u]+we[t]);
                    if(--ind[v] == 0){
                        q.push(v);
                    }
                }
            }
            return dp;
        };
        auto g1 = amog(1,g), gn = amog(n,rg);
        int targ = g1[n];
        for(auto[u,v,t]:rel){
            if(!good[t]) continue;
            if(g1[u]+we[t]+gn[v] == targ){
                //cout << u << " " << v << " " << t << " " << targ << " " << i << "\n";
                cur_good[t] = 1;
            }
        }
        good &= cur_good;
    }*/
    // generate
    /*
    for(int i = 1; i <= ti; i++) cout << good[i];
    cout << "\n";*/
    bool res = rec(0); //assert(res);
    cout << ans.size() << "\n";
    for(int i = 0; i < (int)ans.size(); i++) cout << ans[i]+1 << " \n"[i==(int)ans.size()-1];
    rg.free(); g.free();
}
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