#include<bits/stdc++.h>
#define P pair<long long,int>
#define Pair make_pair
using namespace std;
const int N=100005,M=300005;
const long long INF=1e12;
int T,n,m,ans[N],tot,rcd[M];
int nx[M<<1],fr[M<<1],to[M<<1],ct[M<<1],hd[N],ecnt;
long long dis[N];
bool vis[N];
vector<int> pos[N];
inline int read(){
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9')
		x=(x<<3)+(x<<1)+(c^48), c=getchar();
	return x;
}
inline void add(int u,int v,int w=0){
	nx[++ecnt]=hd[u], hd[u]=ecnt, fr[ecnt]=u, to[ecnt]=v;
	ct[ecnt]=w, pos[w].push_back(ecnt);
}
inline void dfs0(int u){
	for(register int i=hd[u],v,l=0;v=to[i],i;i=nx[i])
		ct[i]=0, dfs0(v);
}
inline void dfs1(int u){
	if(u==n) return void(dis[u]=0);
	dis[u]=0;
	for(register int i=hd[u],v;v=to[i],i;i=nx[i])
		dfs1(v), dis[u]=max(dis[u],dis[v]+ct[i]);
}
inline void dfs2(int u){
	int t=hd[u]; hd[u]=0;
	for(register int i=t,v,l=0;v=to[i],i;i=nx[i])
		if(dis[u]==dis[v]+ct[i]) (!l?hd[u]:nx[l])=i, l=i, dfs2(v);
	nx[hd[u]]=0;
}
inline void Set(int w){
	//cout<<"Set: "<<w<<'\n';
	dfs0(1);
	for(auto i:pos[w]) ct[i]=1;
}
inline void Dijkstra(){
	priority_queue<P,vector<P>,greater<P> > q; q.push(Pair(0,n));
	memset(dis,0x3f,sizeof(dis)), dis[n]=0;
	memset(vis,0,sizeof(vis));
	while(!q.empty()){
		P t=q.top(); q.pop();
		int u=t.second;
		if(vis[u]) continue;
		vis[u]=true;
		for(register int i=hd[u],v;v=to[i],i;i=nx[i])
			if(dis[u]+ct[i]<dis[v])
				dis[v]=dis[u]+ct[i], q.push(Pair(dis[v],v));
	}
}
inline void Print(int u){
	ans[++tot]=u;
	if(u!=n) Print(to[hd[u]]);
}
int main(){
	T=read();
	while(T--){
		n=read(), m=read();
		int mx=0;
		for(register int i=1,u,v,w;i<=m;++i){
			u=read(), v=read(), w=read(), rcd[i]=w;
			add(u,v,w), add(v,u,w), mx=max(mx,w);
		}
		Dijkstra(), dfs2(1), sort(rcd+1,rcd+1+m);
		for(register int i=m;i>=1;--i){
			Set(rcd[i]), dfs1(1), dfs2(1);
			/*
			for(register int i=1;i<=n;++i) cout<<dis[i]<<' ';
			cout<<'\n';
			for(register int u=1;u<=n;++u)
				for(register int i=hd[u],v;v=to[i],i;i=nx[i])
					cout<<u<<' '<<v<<'\n';
			*/
		}
		tot=0, Print(1), printf("%d\n",tot);
		for(register int i=1;i<=tot;++i) printf("%d ",ans[i]);
		putchar('\n');
		ecnt=0;
		for(register int i=1;i<=n;++i) hd[i]=0;
		for(register int i=1;i<=m;++i) pos[rcd[i]].clear();
	}
	return 0;
}