#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 cnt;
    int left, right;
    int prior;
    Node(int val, int cnt): val(val), cnt(cnt), left(-1), right(-1), prior(rand() * RAND_MAX + rand()) {}
    Node() {}
};

Node nodes[3'000'000];
int nodes_cnt = 0;

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

int merge(int A, int B) {
    if (A == -1)
        return B;
    if (B == -1)
        return A;
    if (nodes[A].prior < nodes[B].prior) {
        int ans = node(nodes[A].val, nodes[A].cnt);
        nodes[ans].right = merge(nodes[A].right, B);
        nodes[ans].left = nodes[A].left;
        return ans;
    }
    int ans = node(nodes[B].val, nodes[B].cnt);
    nodes[ans].left = merge(A, nodes[B].left);
    nodes[ans].right = nodes[B].right;
    return ans;
}

pair<int, int> split_by_val(int T, int val) {
    if (T == -1)
        return make_pair(-1, -1);
    if (nodes[T].val < val) {
        auto tmp = split_by_val(nodes[T].right, val);
        int ans = node(nodes[T].val, nodes[T].cnt);
        nodes[ans].right = tmp.first;
        nodes[ans].left = nodes[T].left;
        return make_pair(ans, tmp.second);
    }
    auto tmp = split_by_val(nodes[T].left, val);
    int ans = node(nodes[T].val, nodes[T].cnt);
    nodes[ans].right = nodes[T].right;
    nodes[ans].left = tmp.second;
    return make_pair(tmp.first, ans);
}

int get_min(int T) {
    if (nodes[T].left == -1)
        return T;
    return get_min(nodes[T].left);
}

void print(int T) {
    if (T == -1)
        return;
    print(nodes[T].left);
    cout << nodes[T].val << '#' << nodes[T].cnt << ' ';
    print(nodes[T].right);
}

int insert_val(int T, int x) {
    auto tmp = split_by_val(T, x);
    if (tmp.second != -1) {
        if (nodes[get_min(tmp.second)].val == x) {
            auto tmp2 = split_by_val(tmp.second, x + 1);
            int new_node = node(x, nodes[tmp2.first].cnt + 1);
            int ans = merge(merge(tmp.first, new_node), tmp2.second);
            return ans;
        }
    }
    int new_node = node(x, 1);
    return merge(merge(tmp.first, new_node), tmp.second);
}

void go_down(int T, vector<pair<int, int>>& to) {
    if (T == -1)
        return;
    go_down(nodes[T].left, to);
    to.emplace_back(nodes[T].val, nodes[T].cnt);
    go_down(nodes[T].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;


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] == dist[v] + w) {
                int var = insert_val(dps[v], w);
                if (dps[u] == -2) {
                    dps[u] = var;
                    par[u] = v;
                } else {
                    go_down(var, kek);
                    go_down(dps[u], lol);
                    reverse(kek.begin(), kek.end());
                    reverse(lol.begin(), lol.end());
                    if (cmp(kek, lol)) {
                        par[u] = v;
                        dps[u] = var;
                    }
                    kek.clear();
                    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;
}