#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
    
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 5;
const ll INF = 2e18;

const int maxn = 300010;
const ll inf = 1000000000000000000LL;

int n, m;

int ord[maxn];
int dp[maxn][2];
int topoSort[maxn];
int u[maxn], v[maxn], w[maxn];

bool actived[maxn];

ll dist[maxn][2];

vector<pii> adj[maxn];
vector<pii> dag[maxn], inv[maxn];

void dijkstra(int source, int idDij)
{
    set<pair<ll,int>> s;

    for(int i = 1 ; i <= n ; i++)
        dist[i][idDij] = inf;

    dist[source][idDij] = 0;
    s.insert( { 0 , source } );

    while( !s.empty() )
    {
        int node = s.begin()->second;
        s.erase( s.begin() );

        for(auto [neighbor, id]: adj[node])
        {
            if( dist[neighbor][idDij] > dist[node][idDij] + w[id] )
            {
                s.erase( { dist[neighbor][idDij] , neighbor } );
                dist[neighbor][idDij] = dist[node][idDij] + w[id];
                s.insert( { dist[neighbor][idDij] , neighbor } );
            }
        }
    }
}

void rebuildDAG()
{
    for(int i = 1 ; i <= n ; i++)
        dag[i].clear(), inv[i].clear();

    for(int i = 1 ; i <= m ; i++)
    {
        if( actived[i] )
        {
            dag[ u[i] ].push_back( { v[i] , i } );
            inv[ v[i] ].push_back( { u[i] , i } );
        }
    }
}

void round(int weight)
{
    for(int i = 1 ; i <= n ; i++)
    {
        int node = topoSort[i];
        dp[node][0] = 0;

        for(auto [neighbor, id]: inv[node])
            dp[node][0] = max( dp[node][0] , dp[neighbor][0] + (weight == w[id]));
    }

    for(int i = n ; i > 0 ; i--)
    {
        int node = topoSort[i];
        dp[node][1] = 0;

        for(auto [neighbor, id]: dag[node])
            dp[node][1] = max( dp[node][1] , dp[neighbor][1] + (weight == w[id]));
    }

    for(int i = 1 ; i <= m ; i++)
    {
        if( !actived[i] )
            continue;

        if( dp[ u[i] ][0] + (weight == w[i]) + dp[ v[i] ][1] != dp[n][0] )
            actived[i] = false;
    }

    rebuildDAG();
}

vector<int> findPath()
{
    int node = 1;
    vector<int> path = { 1 };

    while( node != n )
    {
        node = dag[node][0].first;
        path.push_back( node );
    }

    return path;
}

void solve()
{
    cin >> n >> m;

    for(int i = 1 ; i <= n ; i++)
        adj[i].clear();

    for(int i = 1 ; i <= m ; i++)
    {
        cin >> u[i] >> v[i] >> w[i];

        adj[ u[i] ].push_back( { v[i] , i } );
        adj[ v[i] ].push_back( { u[i] , i } );
    }

    dijkstra( 1 , 0 );
    dijkstra( n , 1 );

    for(int i = 1 ; i <= m ; i++)
    {
        actived[i] = false;

        if( dist[ u[i] ][0] + w[i] + dist[ v[i] ][1] == dist[n][0] )
        {
            actived[i] = true;
            continue;
        }

        swap( u[i] , v[i] );

        if( dist[ u[i] ][0] + w[i] + dist[ v[i] ][1] == dist[n][0] )
            actived[i] = true;
    }

    iota( ord + 1 , ord + m + 1 , 1 );
    sort( ord + 1 , ord + m + 1 , [&](int i, int j){
        return w[i] > w[j];
    });

    iota( topoSort + 1 , topoSort + n + 1 , 1 );
    sort( topoSort + 1 , topoSort + n + 1 , [&](int i, int j){
        return dist[i][0] < dist[j][0];
    });

    rebuildDAG();

    for(int i = 1 ; i <= m ; i++)
    {
        int curEdge = ord[i];

        if( !actived[curEdge] )
            continue;

        round( w[curEdge] );
    }

    vector<int> ans = findPath();

    cout << (int)ans.size() << endl;

    for(int x: ans)
        cout << x << " ";

    cout << endl;
}

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

    while( t-- )
        solve();

    return 0;
}