#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005, MAXD = 50005;
int T;
int n, m, k;
vector<pair<int, int>> e[MAXN];
typedef unsigned long long hash_t;
typedef __uint128_t ui;
const hash_t P = 998244353, B = 19260817;
hash_t BASE[MAXN];
struct SegmentTree {
    struct Node {
        int lc, rc;
        hash_t hs;
    } t[MAXN * 17];
    int tot;
    void clear() { tot = 0; }
    int newNode() { ++tot; t[tot].lc = t[tot].rc = t[tot].hs = 0; return tot; }
    void insert(int &p, int d, int l = 1, int r = k) {
        if (!p) p = newNode();
        t[p].hs = ((ui) t[p].hs + BASE[d - l]) % P;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (d <= mid) insert(t[p].lc, d, l, mid);
        else insert(t[p].rc, d, mid + 1, r);
    }
    bool cmp(int p, int q, int d, int e, int l = 1, int r = k) {
        if (l == r) return t[p].hs + (d == l) > t[q].hs + (e == r);
        int mid = (l + r) >> 1;
        if (((ui) t[t[p].rc].hs + (mid < d && d <= r ? BASE[d - mid - 1] : 0)) % P == 
            ((ui) t[t[q].rc].hs + (mid < e && e <= r ? BASE[e - mid - 1] : 0)) % P)
            return cmp(t[p].lc, t[q].lc, d, e, l, mid);
        else
            return cmp(t[p].rc, t[q].rc, d, e, mid + 1, r);
    }
} st;
int dis[MAXN], root[MAXN], pre[MAXN];
bool vis[MAXN];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int main() {
    BASE[0] = 1;
    for (int i = 1; i < MAXN; i++) BASE[i] = (ui) B * BASE[i - 1] % P;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) e[i].clear();
        k = 0;
        for (int i = 1; i <= m; i++) {
            int u, v, c; scanf("%d%d%d", &u, &v, &c);
            k = max(k, c);
            e[u].push_back({ v, c });
            e[v].push_back({ u, c });
        }
        st.clear();
        for (int i = 1; i <= n; i++) root[i] = 0, dis[i] = INT_MAX / 2, pre[i] = 0, vis[i] = 0;
        dis[1] = 0; q.push({ 0, 1 });
        while (!q.empty()) {
            int u = q.top().second; q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            if (u != 1) {
                root[u] = root[pre[u]];
                st.insert(root[u], dis[u] - dis[pre[u]]);
            }
            for (auto [v, c] : e[u]) if (!vis[v]) {
                if (dis[v] > dis[u] + c) {
                    dis[v] = dis[u] + c;
                    pre[v] = u;
                    q.push({ dis[v], v });
                } else if (dis[v] == dis[u] + c) {
                    if (st.cmp(root[u], root[pre[v]], c, dis[v] - dis[pre[v]])) pre[v] = u;
                }
            }
        }
        vector<int> ans;
        int u = n;
        while (u) {
            ans.push_back(u);
            u = pre[u];
        }
        reverse(ans.begin(), ans.end());
        printf("%lu\n", ans.size());
        for (int i : ans) printf("%d ", i);
        printf("\n");
    }
    return 0;
}
/*
2

4 6
1 2 1
1 3 2
2 3 1
2 4 2
3 4 1
1 4 4

6 11
1 2 9
2 3 12
3 4 3
4 5 5
5 6 10
6 1 22
2 4 9
3 6 1
4 6 5
2 5 2
3 5 8
*/