#include <bits/stdc++.h>
#define N 100011
#define ull unsigned long long
#define uint unsigned int
#define pii pair<int,int>
#define s1 first
#define s2 second
using namespace std;
int t,n,m;const int A=50000;
struct edge{int v,w,next;edge(){}edge(int _v,int _w,int _next){v=_v;w=_w;next=_next;}}e[600011];int head[N],Sz;
void init(){memset(head,-1,sizeof(head));Sz=-1;}void insert(int u,int v,int w){e[++Sz]=edge(v,w,head[u]);head[u]=Sz;}
ull hsh[N*30],pw[N];int lc[N*30],rc[N*30],sz;
void pushup(int x,int L,int R)
{
	hsh[x]=hsh[lc[x]]*pw[R-(L+R>>1)]+hsh[rc[x]];
}
void add(int k,int p,int L,int R,int x,int &c)
{
	if(!c)c=++sz,lc[c]=rc[c]=hsh[c]=0;
	if(L==R){hsh[c]=hsh[x]+p;return;}
	if(k<=L+R>>1)add(k,p,L,L+R>>1,lc[x],lc[c]),rc[c]=rc[x];else add(k,p,(L+R>>1)+1,R,rc[x],rc[c]),lc[c]=lc[x];
	pushup(c,L,R);
}
void add0(int k,int p,int L,int R,int &x)
{
	if(!x)x=++sz,lc[x]=rc[x]=hsh[x]=0;
	if(L==R){hsh[x]+=p;return;}
	if(k<=L+R>>1)add0(k,p,L,L+R>>1,lc[x]);else add0(k,p,(L+R>>1)+1,R,rc[x]);pushup(x,L,R);
}
bool query(int x1,int x2,int L,int R)
{//printf("query(%d,%d,[%d,%d]) rhash:%llu %llu\n",x1,x2,L,R,hsh[rc[x1]],hsh[rc[x2]]);
	if(L==R)return hsh[x1]>hsh[x2];
	if(hsh[rc[x1]]==hsh[rc[x2]])return query(lc[x1],lc[x2],L,L+R>>1);
	else return query(rc[x1],rc[x2],(L+R>>1)+1,R);
}
uint dis[N];bool vis[N];
struct node{int v;uint d;node(){}node(int _v,uint _d){v=_v;d=_d;}};
bool operator<(node a,node b){return a.d>b.d;}
priority_queue<node> pq;
void dijkstra()
{
	for(int i=1;i<=n;++i)dis[i]=4e9,vis[i]=0;
	pq.push(node(1,0));dis[1]=0;
	while(!pq.empty())
	{
		int p=pq.top().v;pq.pop();if(vis[p])continue;vis[p]=1;
		for(int i=head[p];~i;i=e[i].next)if(dis[e[i].v]>dis[p]+e[i].w)
		{
			dis[e[i].v]=dis[p]+e[i].w;
			pq.push(node(e[i].v,dis[e[i].v]));
		}
	}
}
int pre[N],preW[N],rt[N];pair<uint,int> nd[N];
void sssp()
{
	for(int i=1;i<=n;++i)nd[i]=pii(dis[i],i),pre[i]=preW[i]=-1,rt[i]=0;sz=0;
	sort(nd+1,nd+1+n);
	for(int i=1;i<=n;++i)
	{
		int x=nd[i].s2;
		if(~pre[x])add(preW[x],1,1,A,rt[pre[x]],rt[x]);
		for(int _=head[x];~_;_=e[_].next)if(dis[e[_].v]==dis[x]+e[_].w)
		{
			if(!~pre[e[_].v])
			{
				pre[e[_].v]=x;preW[e[_].v]=e[_].w;
			}
			else
			{
				add0(e[_].w,1,1,A,rt[x]);
				add0(preW[e[_].v],1,1,A,rt[pre[e[_].v]]);
				// printf("comparing %d->%d +%d and %d->%d +%d\n",x,e[_].v,e[_].w,pre[e[_].v],e[_].v,preW[e[_].v]);
				bool flg=query(rt[x],rt[pre[e[_].v]],1,A);
				add0(e[_].w,-1,1,A,rt[x]);
				add0(preW[e[_].v],-1,1,A,rt[pre[e[_].v]]);
				if(flg)pre[e[_].v]=x,preW[e[_].v]=e[_].w;
			}
		}
	}
}
vector<int> ans;
int main()
{
	scanf("%d",&t);while(t--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i)head[i]=-1;Sz=0;
		for(int i=1;i<=m;++i)
		{
			int u,v,w;scanf("%d%d%d",&u,&v,&w);
			insert(u,v,w);insert(v,u,w);
		}
		dijkstra();
		sssp();
		int U=n;
		while(U!=1)ans.push_back(U),U=pre[U];
		ans.push_back(1);
		printf("%d\n",int(ans.size()));
		while(!ans.empty())printf("%d ",ans.back()),ans.pop_back();putchar(10);
	}return 0;
}