#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() {}
};

Node nodes[5'120'000];
int nodes_cnt = 0;

int node(int val) {
    nodes[nodes_cnt] = Node(val);
    ++nodes_cnt;
    return nodes_cnt - 1;
}

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

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 ans = node(val(T) + 1);
    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);
    else
        nodes[ans].right = add(get_right(T), mid, right, x);
    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);
        return;
    }
    int mid = (left + right) / 2;
    go_down(nodes[T].left, left, mid, to);
    go_down(nodes[T].right, mid, right, to);
}

bool cmp(const vector<pair<int, int>>& first, const vector<pair<int, int>>& second) {
    int i = 0, takeni = 0;
    int j = 0, takenj = 0;
    while (i < first.size() && j < second.size()) {
        if (first[i].first != second[j].first) {
            return first[i].first > second[j].first;
        }
        int take = min(first[i].second - takeni, second[j].second - takenj);
        takeni += take;
        takenj += take;
        if (first[i].second == takeni) {
            takeni = 0;
            ++i;
        }
        if (second[j].second == takenj) {
            takenj = 0;
            ++j;
        }
    }
    // the same
    if (i == first.size() && j == second.size())
        return false;
    // first is prefix of second
    if (i == first.size())
        return false;
    // second is prefix of first
    return true;
}

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

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

const int MX = 50'050;

void solve() {
    int n, m;
    cin >> n >> m;
    nodes_cnt = 0;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        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);
            }
        }
    }
    vector<int> dps(n, -2);
    vector<int> 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;
}