#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#define N 100000
#define M 100
#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],p[N+1],pv[N+1],pvt[N+1],dst[N+1],dp[N+1][M+1];
vector<reads>E[N+1];
vector<int>A;
vector<int>B;
bool used[N+1];
bool cmp(int x,int y)
{
    return x>y;
}
bool cmp2(int x,int y)
{
    return dis[x]<dis[y];
}
void dijkstra()
{
    int top;
    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;
}
int main()
{
    int x,y,z,op;
    T=read();
    while (T--)
    {
	n=read(),m=read(),length=0;
	for (int i=1;i<=n;++i)
	{
	    E[i].clear(),dis[i]=inf,used[i]=pv[i]=pvt[i]=dst[i]=0;
	    for (int j=1;j<=100;++j) dp[i][j]=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();
	for (int i=1;i<=n;++i) p[i]=i;
	sort(p+1,p+n+1,cmp2);
	for (int i=2;i<=n;++i)
	    if (dis[p[i]]<=dis[n])
	    {
		for (int j=0;j<E[p[i]].size();++j)
		    if (dis[E[p[i]][j].num]+E[p[i]][j].data==dis[p[i]])
		    {
			if (!pv[p[i]])
			{
			    pv[p[i]]=E[p[i]][j].num;
			    for (int k=1;k<=100;++k) dp[p[i]][k]=dp[E[p[i]][j].num][k];
			    if (E[p[i]][j].data<=100) pvt[p[i]]=pvt[E[p[i]][j].num],dst[p[i]]=dst[E[p[i]][j].num],dp[p[i]][E[p[i]][j].data]++;
			    else pv[p[i]]=E[p[i]][j].num,dst[p[i]]=E[p[i]][j].data;
			}
			else
			{
			    A.clear(),B.clear(),x=p[i];
			    while (pvt[x]) A.push_back(dst[x]),x=pvt[x];
			    x=E[p[i]][j].num;
			    while (pvt[x]) B.push_back(dst[x]),x=pvt[x];
			    if (E[p[i]][j].data>100) B.push_back(E[p[i]][j].data);
			    sort(A.begin(),A.end(),cmp),sort(B.begin(),B.end(),cmp),op=-1;
			    for (int k=0;k<min(A.size(),B.size());++k)
				if (A[k]!=B[k])
				{
				    if (A[k]>B[k])
				    {
					op=0;
					break;
				    }
				    else
				    {
					op=1;
					break;
				    }
				}
			    if (A.size()!=B.size()) op=(A.size()<B.size());
			    if (op==-1)
			    {
				for (int k=100;k>=1;--k)
				    if (dp[E[p[i]][j].num][k]+(k==E[p[i]][j].data)!=dp[p[i]][k])
				    {
					if (dp[E[p[i]][j].num][k]+(k==E[p[i]][j].data)>dp[p[i]][k])
					{
					    op=1;
					    break;
					}
					else
					{
					    op=0;
					    break;
					}
				    }
			    }
			    if (op==1)
			    {
				pv[p[i]]=E[p[i]][j].num;
				for (int k=1;k<=100;++k) dp[p[i]][k]=dp[E[p[i]][j].num][k];
				if (E[p[i]][j].data<=100) pvt[p[i]]=pvt[E[p[i]][j].num],dst[p[i]]=dst[E[p[i]][j].num],dp[p[i]][E[p[i]][j].data]++;
				else pv[p[i]]=E[p[i]][j].num,dst[p[i]]=E[p[i]][j].data;
			    }
			}
		    }
	    }
	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;
}