#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cassert>
#define N 100000
#define inf 1e9
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
struct reads
{
    int num,data;
    bool operator < (const reads &t)const
    {
	return data>t.data; 
    }
};
priority_queue<reads>q;
int T,n,m,tong[N+1],length,dis[N+1],dis2[N+1],pv[N+1],in[N+1],dque[N+1],top;
bool used[N+1];
vector<reads>E[N+1];
vector<reads>ES[N+1];
vector<reads>dist[N+1];
vector<reads>c;
void adder(vector<reads>&a,int b)
{
    int ps=-1;
    for (int i=0;i<a.size();++i)
	if (a[i].num==b)
	{
	    c=a,c[i].data++;
	    return;
	}
    for (int i=0;i<a.size();++i)
	if (a[i].num>b)
	    ps=i;
    for (int i=0;i<=ps;++i) c.push_back(a[i]);
    c.push_back((reads){b,1});
    for (int i=ps+1;i<a.size();++i) c.push_back(a[i]);
    return;
}
bool operator > (vector<reads>&a,vector<reads>&b)
{
    for (int i=0;i<min(a.size(),b.size());++i)
	if (a[i].num!=b[i].num||a[i].data!=b[i].data)
	{
	    if (a[i].num>b[i].num||(a[i].num==b[i].num&&a[i].data>b[i].data)) return 1;
	    else return 0;
	}
    return a.size()>b.size();
}
bool cmp2(int x,int y)
{
    return dis[x]<dis[y];
}
void dijkstra()
{
    int top;
    for (int i=1;i<=n;++i) dis[i]=inf,used[i]=0;
    dis[1]=0,q.push((reads){1,0});
    while (!q.empty())
    {
	top=q.top().num,q.pop();
	if (used[top]) continue;
	used[top]=1;
	for (int i=0;i<E[top].size();++i)
	    if (dis[E[top][i].num]>dis[top]+E[top][i].data)
		dis[E[top][i].num]=dis[top]+E[top][i].data,q.push((reads){E[top][i].num,dis[E[top][i].num]});
    }
    return;
}
void dijkstra2()
{
    int top;
    for (int i=1;i<=n;++i) dis2[i]=inf,used[i]=0;
    dis2[n]=0,q.push((reads){n,0});
    while (!q.empty())
    {
	top=q.top().num,q.pop();
	if (used[top]) continue;
	used[top]=1;
	for (int i=0;i<E[top].size();++i)
	    if (dis2[E[top][i].num]>dis2[top]+E[top][i].data)
		dis2[E[top][i].num]=dis2[top]+E[top][i].data,q.push((reads){E[top][i].num,dis2[E[top][i].num]});
    }
    return;
}
void topo_sort()
{
    int top;
    queue<int>q;
    q.push(1);
    while (!q.empty())
    {
	top=q.front(),q.pop();
	for (int i=0;i<ES[top].size();++i)
	{
	    in[ES[top][i].num]--;
	    if (!in[ES[top][i].num]) q.push(ES[top][i].num);
	    adder(dist[top],ES[top][i].data);
	    if (c>dist[ES[top][i].num]) dist[ES[top][i].num]=c,pv[ES[top][i].num]=top;
	    c.clear(),c.shrink_to_fit();
	}
        dist[top].clear(),dist[top].shrink_to_fit();
    }
    return;
}
int main()
{
    int x,y,z;
    T=read();
    while (T--)
    {
	n=read(),m=read(),length=0;
	for (int i=1;i<=n;++i) E[i].clear(),ES[i].clear(),dist[i].clear(),in[i]=0;
	for (int i=1;i<=m;++i) x=read(),y=read(),z=read(),E[x].push_back((reads){y,z}),E[y].push_back((reads){x,z});
	dijkstra(),dijkstra2();
	for (int i=1;i<=n;++i) used[i]=(dis[i]+dis2[i]==dis[n]);
	for (int i=1;i<=n;++i)
	    if (used[i])
		for (int j=0;j<E[i].size();++j)
		    if (used[E[i][j].num]&&dis[i]+E[i][j].data==dis[E[i][j].num])
			ES[i].push_back(E[i][j]),in[E[i][j].num]++;
	topo_sort(),x=n,tong[++length]=n;
	while (x!=1) x=pv[x],tong[++length]=x;
	printf("%d\n",length);
	for (int i=length;i>=1;--i) printf("%d ",tong[i]);
	puts("");
    }
    return 0;
}