#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
// #define int long long
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
#define BOOST ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);  
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<ll> vll;

// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
const ll INF = 1e18;
vll dijkstra(vector<vii> &adj, int start) {
    int n = adj.size() - 1;
    vll dist(n + 1, INF);

    priority_queue<pair<int,ll>, vector<pair<int,ll>>, function<bool(pair<int,ll>&, pair<int,ll>&)>>
        pq([&](pair<int,ll> &p1, pair<int,ll> &p2) {
            return p1.second > p2.second; 
        });
    dist[start] = 0;
    pq.push({start, dist[start]});
    while(pq.size() > 0) {
        auto p = pq.top();
        pq.pop();

        if(dist[p.first] != p.second) {
            continue;
        }
        for(auto p2 : adj[p.first]) {
            if(dist[p.first] + p2.second < dist[p2.first]) {
                dist[p2.first] = dist[p.first] + p2.second;
                pq.push({p2.first, dist[p2.first]});
            }
        }
    }
    return dist;
}
vector<int> toposort(vector<vii> &adj) {
    int n = adj.size() - 1;
    vector<int> res;
    vector<int> deg(n + 1, 0);
    vector<int> cur;
    for(int u = 1; u <= n; u++) {
        for(auto p : adj[u]) {
            deg[p.first]++;
        }
    }
    for(int u = 1; u <= n; u++) {
        if(deg[u] == 0) {
            cur.pb(u), res.pb(u);
        }
    }
    while(cur.size() > 0) {
        int u = cur.back();
        cur.pop_back();

        for(auto p : adj[u]) {
            deg[p.first]--;
            if(deg[p.first] == 0) {
                cur.pb(p.first), res.pb(p.first);
            }
        }
    }
    if((int)res.size() != n) {
        assert(false);
    }
    return res;
}
bool bigger_lex(vi &v1, vi &v2) {
    for(int i = 0; i < (int)min(v1.size(), v2.size()); i++) {
        if(v1[i] > v2[i]) return true;
        else if(v1[i] < v2[i]) return false;
    }
    return v1.size() > v2.size();
}
void radix_sort(vi &v) {
    int n = v.size();
    vi p(n, 0);
    iota(all(p), 0);
    for(int i = 0; i < 5; i++) {
        vi cnt(10, 0), p2(n, 0);
        for(int j = 0; j < n; j++) {
            int d = (int)(v[j] / pow(10, i)) % 10;
            cnt[d]++;
        }
        for(int j= 1; j < 10; j++) cnt[j] += cnt[j - 1];
        
        for(int j = n-1; j >= 0; j--) {
            int d = (int)(v[p[j]] / pow(10, i)) % 10;
            p2[--cnt[d]] = p[j]; 
        }
        p = p2;
    }
    vi tmp = v;
    for(int i = 0; i < n; i++) {
        v[i] = tmp[p[n - i - 1]];
    }
}
void test_case() {
    int n, m;
    cin >> n >> m;
    vector<vii> adj(n + 1, vii());

    for(int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
    }

    vll dist1 = dijkstra(adj, 1), dist2 = dijkstra(adj, n);
    vector<vii> adj2(n + 1, vii());
    for(int u = 1; u <= n; u++) {
        for(auto p : adj[u]) {
            int v = p.first, c = p.second;
            if(dist1[u] + c + dist2[v] == dist1[n]) {
                adj2[u].pb({v, c});
            }
        }
    }
    adj.clear();
    adj = adj2;
    adj2.clear();
    vector<int> topo = toposort(adj);
    vector<pair<int,int>> nxt(n + 1, {-1, -1});
    for(int rep = n - 1; rep >= 0; rep--) {
        int u = topo[rep];
        pair<int,int> best_arg = {-1, -1};
        vi best{};
        for(auto p : adj[u]) {
            vi path{p.second};
            int cur = p.first;
            while(nxt[cur].first != -1) {
                path.pb(nxt[cur].second);
                cur = nxt[cur].first;
            }
            radix_sort(path);
            if(bigger_lex(path, best)) {
                best = path, best_arg = p;
            }
        }
        nxt[u] = best_arg;
    }
    vi ans{1};
    int cur = 1;
    while(nxt[cur].first != -1) {
        ans.pb(nxt[cur].first);
        cur = nxt[cur].first;
    }
    cout << ans.size() << "\n";
    for(auto x : ans) {
        cout << x << " ";
    }
    cout << "\n";
}
int32_t main() {
    BOOST;

    int tc = 1;
    cin >> tc;
    while(tc--) {
        test_case();
    }
    return 0;
}