#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

struct Node {
    int val;
    int left, right;
    Node(int val): val(val), left(-1), right(-1) {}
    Node() {}
};

const int MXNODES = 3'000'000;
const int USED = 1 << 22;
const int MAXN = 100100;
Node nodes[MXNODES];
int extras[17];
int nodes_cnt = 0;

const int MX = 50'050;

int dps[MAXN];
int par[MAXN];

void dfs(int t) {
    if (t < 0)
        return;
    if (nodes[t].val & USED)
        return;
    nodes[t].val |= USED;
    dfs(nodes[t].left);
    dfs(nodes[t].right);
}

int n;

void collect_garbage() {
    for (int i = 0; i < MXNODES; ++i)
        nodes[i].val = (nodes[i].val & (~USED));
    for (int i = 0; i < n; ++i) {
        dfs(dps[i]);
    }
    for (int i = 0; i < 17; ++i)
        dfs(extras[i]);
}

int node(int val) {
    while (true) {
        if (nodes_cnt == MXNODES) {
            collect_garbage();
            nodes_cnt = 0;
        }
        if (!(nodes[nodes_cnt].val & USED)) {
            break;
        }
        ++nodes_cnt;
    }
    nodes[nodes_cnt] = Node(val);
    ++nodes_cnt;
    return nodes_cnt - 1;
}

int val(int T) {
    return T == -1 ? 0 : (nodes[T].val ^ USED);
}

int get_left(int T) {
    return T == -1 ? -1 : nodes[T].left;
}

int get_right(int T) {
    return T == -1 ? -1 : nodes[T].right;
}


int add(int T, int left, int right, int x, int w = 0) {
    int ans = node(val(T) + 1 + USED);
    extras[w] = ans;
    nodes[ans].left = get_left(T);
    nodes[ans].right = get_right(T);
    if (left + 1 == right)
        return ans;
    int mid = (left + right) / 2;
    if (x < mid)
        nodes[ans].left = add(get_left(T), left, mid, x, w + 1);
    else
        nodes[ans].right = add(get_right(T), mid, right, x, w + 1);
    return ans;
}

void go_down(int T, int left, int right, vector<pair<int, int>>& to) {
    if (T == -1)
        return;
    if (left + 1 == right) {
        to.emplace_back(left, nodes[T].val ^ USED);
        return;
    }
    int mid = (left + right) / 2;
    go_down(nodes[T].right, mid, right, to);
    go_down(nodes[T].left, left, mid, to);
}

bool cmp(const vector<pair<int, int>>& first, const vector<pair<int, int>>& second) {
    for (int i = 0; i < first.size() && i < second.size(); ++i) {
        if (first[i] != second[i]) {
            return first[i] > second[i];
        }
    }
    return first.size() > second.size();
}

const int INF = 1e5;
vector<pair<int, int>> G[MAXN];

vector<pair<int, int>> kek;
vector<pair<int, int>> lol;

void solve() {
    fill(extras, extras + 17, -1);

    int m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        
        /*if (i < n)
            u = i, v = (i + 1) % n;
        else {
            u = rand() % n;
            v = rand() % n;
            while (v == u)
                v = rand() % n;
        }
        w = abs(u - v);*/
        
        //cerr << u << ' ' << v << '\n';

        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    vector<int> dist(n, INF);
    dist[0] = 0;
    set<pair<int, int>> Q;
    vector<int> order;
    Q.emplace(0, 0);
    while (!Q.empty()) {
        int v = Q.begin()->second;
        order.emplace_back(v);
        Q.erase(Q.begin());
        for (auto [u, w] : G[v]) {
            if (dist[u] > dist[v] + w) {
                Q.erase(make_pair(dist[u], u));
                dist[u] = dist[v] + w;
                Q.emplace(dist[u], u);
            }
        }
    }
    fill(dps, dps + n, -2);
    fill(par, par + n, -1);
    dps[0] = -1;
    for (int v : order) {
        for (auto [u, w] : G[v]) {
            if (dist[u] + w == dist[v]) {
                // cur is lol
                int var = add(dps[u], 0, MX, w);
                kek.clear();
                go_down(var, 0, MX, kek);
                if (dps[v] == -2) {
                    swap(lol, kek);
                    par[v] = u;
                    dps[v] = var;
                } else {
                    if (cmp(kek, lol)) {
                        swap(lol, kek);
                        par[v] = u;
                        dps[v] = var;
                    }
                }
            }
        }
        lol.clear();
    }
    int cur = n - 1;
    vector<int> ans;
    while (cur != 0) {
        ans.emplace_back(cur);
        cur = par[cur];
    }
    ans.emplace_back(0);
    reverse(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (int x : ans)
        cout << x + 1 <<  ' ';
    cout << '\n';
    for (int i = 0; i < n; ++i) {
        G[i].clear();
    }
}


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

    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }
    
    return 0;
}