#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> pr;
const int N=1e5+5;
const int M=3e5+5;
const int INF=50005;
int n,m;
int Head[N],Nxt[M<<1],ver[M<<1],val[M<<1],cnt_edge;
int ind[N];
int uu[M<<1],vv[M<<1],vall[M<<1],cnt;
int dist[N];
inline int Read(){
	char ch;
	int f=1;
	while((ch=getchar())<'0'||ch>'9')
		if(ch=='-') f=-1;
	int x=ch^48;
	while((ch=getchar())>='0'&&ch<='9')
		x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
inline void print(int x){
	if(x>=10) print(x/10);
	putchar(x%10+48);
	return ;
}
inline void Print(int x,char ch='\n'){
	if(x<0){
		putchar('-');
		print(-x);
	}
	else print(x);
	putchar(ch);
	return ;
}
inline void Add(int u,int v,int value){
	++cnt_edge;
	ver[cnt_edge]=v;
	val[cnt_edge]=value;
	Nxt[cnt_edge]=Head[u];
	Head[u]=cnt_edge;
	return ;
}
inline void Add_Edge(int u,int v,int value){
	Add(u,v,value);
	Add(v,u,value);
	ind[v]++;
	return ;
}
inline void Init(){
	cnt=0;
	n=Read();
	cnt_edge=-1;
	for(int i=1;i<=n;i++){
		Head[i]=-1;
		dist[i]=INF;
	}
	for(m=Read();m;m--){
		int u=Read(),v=Read();
		int value=Read();
		Add_Edge(u,v,value);
		++cnt;
		uu[cnt]=u;
		vv[cnt]=v;
		vall[cnt]=value;
		++cnt;
		uu[cnt]=v;
		vv[cnt]=u;
		vall[cnt]=value;
	}
	return ;
}
priority_queue<pr,vector<pr>,greater<pr> >q;
bool vis[N];
inline void Dij(){
	for(int i=1;i<=n;i++)
		vis[i]=0;
	dist[1]=0;
	q.push(make_pair(0,1));
	while(q.size()){
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue ;
		vis[u]=1;
		//printf("u=%d\n",u);
		for(int i=Head[u];i!=-1;i=Nxt[i]){
			int v=ver[i];
			//printf("v=%d\n",v);
			if(dist[v]>dist[u]+val[i]){
				dist[v]=dist[u]+val[i];
				q.push(make_pair(dist[v],v));
			}
		}
	}
	for(int i=1;i<=n;i++)
		vis[i]=0;
	for(int i=1;i<=n;i++){
		Head[i]=-1;
		ind[i]=0;
	}
	cnt_edge=-1;
	for(int i=1;i<=cnt;i++){
		int u=uu[i],v=vv[i];
		if(dist[v]==dist[u]+vall[i]) Add_Edge(u,v,vall[i]),vis[vall[i]]=1;
	}
	return ;
}
queue<int>que;
int to[N];
inline void Dfs(int u,int x){
	if(to[u]!=-1) return ;
	to[u]=0;
	for(int i=Head[u];i!=-1;i=Nxt[i]){
		if(i%2==1) continue ;
		int v=ver[i];
		if(dist[v]!=dist[u]+(val[i]==x)) continue ;
		Dfs(v,x);
		to[u]=to[u]||to[v];
	}
	return ;
}
inline void Bfs(int x){
	//printf("x=%d\n",x);
	cnt=0;
	for(int i=0;i<=cnt_edge;i+=2){
		int v=ver[i],u=ver[i^1];
		vis[val[i]]=0;
		++cnt;
		uu[cnt]=u;
		vv[cnt]=v;
		vall[cnt]=val[i];
	}
	for(int i=1;i<=n;i++)
		dist[i]=0;
	dist[1]=0;
	que.push(1);
	while(que.size()){
		int u=que.front();
		que.pop();
		for(int i=Head[u];i!=-1;i=Nxt[i]){
			if(i%2==1) continue ;
			int v=ver[i];
			int dis=dist[u]+(val[i]==x);
			if(dis>dist[v]) dist[v]=dis;
			--ind[v];
			if(ind[v]==0) que.push(v);
		}
	}
	for(int i=1;i<=n;i++)
		to[i]=-1;
	to[n]=1;
	for(int i=1;i<n;i++)
		Dfs(i,x);
	for(int i=1;i<=n;i++){
		Head[i]=-1;
		ind[i]=0;
	}
	cnt_edge=-1;
	for(int i=1;i<=cnt;i++){
		int u=uu[i],v=vv[i];
		if(to[u]==1&&to[v]==1&&dist[v]==dist[u]+(vall[i]==x)) Add_Edge(u,v,vall[i]),vis[vall[i]]=1;
	}
	return ;
}
int pre[N];
inline void Dfs(int u){
	vis[u]=1;
	for(int i=Head[u];i!=-1;i=Nxt[i]){
		if(i%2==1) continue ;
		int v=ver[i];
		if(vis[v]) continue ;
		pre[v]=u;
		Dfs(v);
	}
	return ;
}
int ans;
inline void Find(int u){
	ans++;
	if(u==1){
		Print(ans);
		Print(u,' ');
		return ;
	}
	Find(pre[u]);
	Print(u,' ');
	return ;
}
inline void Solve(){
	Dij();
	//Print(dist[n]);
	for(int i=50000;i;i--)
		if(vis[i]) Bfs(i);
	for(int i=1;i<=cnt;i++)
		vis[vall[i]]=0;
	Dfs(1);
	ans=0;
	Find(n);
	for(int i=1;i<=n;i++)
		vis[i]=0;
	putchar('\n');
	return ;
}
int T;
#include<ctime>
int main(){
	//#define LOCAL
	#ifdef LOCAL
	int st=clock();
	#endif
	for(T=Read();T;T--){
		Init();
		Solve();
	}
	#ifdef LOCAL
	int en=clock();
	printf("cost %d ms\n",en-st);
	#endif
	return 0;
}