#include<cstdio>
#include<queue>
#include<utility>
#include<iostream>
using namespace std;
const int o=3e5+10;
int z,n,m,h[o],cnt,dis[o],dis2[o],d[o],topo[o],st[o],tp;bool vis[o],deln[o],dele[o],flg;
priority_queue<pair<int,int> > q;queue<int> Q;
struct Edge{int v,p,w;}e[o*2];
inline void ad(int U,int V,int W){e[++cnt].v=V;e[cnt].p=h[U];e[h[U]=cnt].w=W;}
inline void dijkstra(int S,int*dis){
	for(int i=1;i<=n;++i) dis[i]=o,vis[i]=0;
	for(q.push(make_pair(dis[S]=0,S));!q.empty();){
		int t=q.top().second;
		q.pop();
		if(vis[t]) continue;
		vis[t]=1;
		for(int i=h[t];i;i=e[i].p)
			if(dis[e[i].v]>dis[t]+e[i].w) q.push(make_pair(-(dis[e[i].v]=dis[t]+e[i].w),e[i].v));
	}
}
void dfs(int nw){
	if(vis[nw]||flg) return;
	vis[nw]=1;
	if((st[++tp]=nw)==n){
		printf("%d\n",tp);flg=1;
		for(int i=1;i<=tp;++i) printf("%d ",st[i]);
		--tp;
		return;
	}
	for(int i=h[nw];i;i=e[i].p) if(!dele[i]) dfs(e[i].v);
	--tp;
}
int main(){
	for(scanf("%d",&z);z--;putchar('\n'),cnt=flg=0){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i) h[i]=0;
		for(int i=1,u,v,w;i<=m;++i) scanf("%d%d%d",&u,&v,&w),ad(u,v,w),ad(v,u,w);
		dijkstra(1,dis);dijkstra(n,dis2);
		for(int i=1;i<=n;++i) deln[i]=(dis[i]+dis2[i]!=dis[n]);
		for(int i=1;i<=n;++i) for(int j=h[i];j;j=e[j].p) if(!(dele[j]=(dis[i]+e[j].w!=dis[e[j].v]))) ++d[e[j].v];
		for(cnt=0,Q.push(1);!Q.empty();topo[++cnt]=Q.front(),Q.pop())
			for(int i=h[Q.front()];i;i=e[i].p) if(!dele[i]) if(!--d[e[i].v]) Q.push(e[i].v);
		for(int w;1;){
			w=0;
			for(int i=1;i<=n;++i) if(!deln[i]) for(int j=h[i];j;j=e[j].p) if(!deln[e[j].v]&&!dele[j]) w=max(w,e[j].w);
			if(!w) break;
			for(int i=1;i<=n;++i) dis[i]=dis2[i]=0;
			for(int i=1;i<=cnt;++i) for(int j=h[topo[i]];j;j=e[j].p)
				if(!dele[j]) dis[e[j].v]=max(dis[e[j].v],dis[topo[i]]+(e[j].w==w));
			for(int i=cnt;i;--i) for(int j=h[topo[i]];j;j=e[j].p)
				if(!dele[j]&&!deln[e[j].v]) dis2[topo[i]]=max(dis2[topo[i]],dis2[e[j].v]+(e[j].w==w));
			for(int i=1;i<=n;++i) for(int j=h[i];j;j=e[j].p){
				if(dis[i]+dis2[e[j].v]+(e[j].w==w)<dis[n]) dele[j]=1;
				if(e[j].w==w) e[j].w=0;
			}
		}
		for(int i=1;i<=n;++i) vis[i]=0;
		dfs(1);
	}
	return 0;
}