#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
vector<int> pai, sub, Dist[2], pai2;
vector<vector<pair<int, int>>> grafo;
vector<vector<int>> grafo2;

int find(int v) {return pai[v] = (v == pai[v] ? v : find(pai[v]));}
void une(int x, int y)
{
    x = find(x); y = find(y);
    if (x == y) return;
    if (sub[x] < sub[y]) swap(x, y);
    pai[y] = x;
    sub[x] += sub[y];
}

void dijkstra(int S, int type)
{
    // cerr << "ERRO " << type << '\n';
    set<pair<int, int>> fora;
    fora.emplace(0, S); Dist[type][S] = 0;

    while (!fora.empty())
    {
        auto [d, v] = *fora.begin(); fora.erase(fora.begin());
        // cerr << '\t' << v << " " << d << '\n';

        for (auto [viz, p] : grafo[v])
        {
            if (Dist[type][viz] > d + p)
            {
                fora.erase(make_pair(Dist[type][viz], viz));
                fora.emplace(Dist[type][viz] = d + p, viz);
            }
        }
    }
}

void dfs(int v, int p)
{
    // cerr << "ERRO " << 2 << '\n';
    pai2[v] = p;

    for (auto viz : grafo2[v])
    {
        if (viz == p) continue;
        dfs(viz, v);
    }
}

void solve()
{
    int N, M;
    cin >> N >> M;
    // cerr << N << " " << M << '\n';
    // cerr << "ERRO " << 3 << '\n';
    //Limpar as coisas
    {
        pai.resize(N+1); iota(pai.begin(), pai.end(), 0);
        sub.resize(N+1); fill(sub.begin(), sub.end(), 1);
        pai2.resize(N+1);
        grafo.clear(); grafo.resize(N+1);
        grafo2.clear(); grafo2.resize(N+1);
        Dist[0].resize(N+1); fill(Dist[0].begin(), Dist[0].end(), INF);
        Dist[1].resize(N+1); fill(Dist[1].begin(), Dist[1].end(), INF);
    }
    vector<tuple<int, int, int>> arestas(M);
    for (auto &[P, X, Y] : arestas)
    {
        cin >> X >> Y >> P;
        grafo[X].emplace_back(Y, P);
        grafo[Y].emplace_back(X, P);
    }
    // cerr << "ERRO " << 4 << '\n';
    dijkstra(1, 0); dijkstra(N, 1);

    // cerr << "ERRO " << 6 << '\n';
    for (int i = 0; i < arestas.size(); i++)
    {
        auto [P, X, Y] = arestas[i];
        if (Dist[0][X] + P + Dist[1][Y] == Dist[0][N]) continue;
        if (Dist[0][Y] + P + Dist[1][X] == Dist[0][N]) continue;
        swap(arestas.back(), arestas[i]);
        arestas.pop_back(); --i;
    }

    sort(arestas.rbegin(), arestas.rend());

    // cerr << "ERRO " << 5 << '\n';
    for (auto [P, X, Y] : arestas)
    {
        if (find(X) == find(Y)) continue;
        une(X, Y);
        grafo2[X].push_back(Y);
        grafo2[Y].push_back(X);
    }
    dfs(1, 1);

    // cerr << "ERRO " << 7 << '\n';
    int x = N; vector<int> resp(1, N);
    while (pai2[x] != x)
    {
        x = pai2[x];
        resp.push_back(x);
    }
    reverse(resp.begin(), resp.end());
    cout << resp.size() << '\n';
    for (auto r : resp) cout << r << " ";
    cout << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    while (T--) solve();
}