#include<bits/stdc++.h>
#define ll long long
#define ust int
#define fi first
#define sc second
using namespace std;
pair<ust,ust> M[14000000];
int cnt;
ust dis[100002];
int lst[100002],n,bg[100002],ed[100002];
ust lstl[100002];
int fir[100002],to[600002],nxt[600002],TOT;ust w[600002];
void add(int u,int v,ust ww)
{
	TOT++;nxt[TOT]=fir[u];fir[u]=TOT,to[TOT]=v;w[TOT]=ww;
	swap(u,v);
	TOT++;nxt[TOT]=fir[u];fir[u]=TOT,to[TOT]=v;w[TOT]=ww;
}
pair<ust,ust> T[2][100002];int tot[2];
void gt(int tg,int x,ust o)
{
	tot[tg]=0;
	for (int i=bg[x];i<ed[x];i++) if (M[i].fi>o)
	{
		T[tg][tot[tg]++]=M[i];
	}
	else if (M[i].fi==o)
	{
		T[tg][tot[tg]]=M[i];T[tg][tot[tg]++].sc++;
	}else
	{
		if (tot[tg]==0 || T[tg][tot[tg]-1].fi>o)
		{
			T[tg][tot[tg]++]={o,1};
		}
		T[tg][tot[tg]++]=M[i];
	}
	if (tot[tg]==0 || T[tg][tot[tg]-1].fi>o)
	{
		T[tg][tot[tg]++]={o,1};
	}
	//cout<<x<<' '<<o<<':'<<endl;
	//for (int i=0;i<tot[tg];i++) cout<<T[tg][i].fi<<' '<<T[tg][i].sc<<endl;
}
int chk(int x,int y,int z,ust ox,ust oy)
{
	gt(0,x,ox);
	gt(1,y,oy);
	int i;
	for (i=0;i<tot[0] && i<tot[1];i++)
	{
		if (T[0][i]!=T[1][i])
		{
			if (T[0][i]<T[1][i]) return 1;
			else return 0;
		}
	}
	return 0;
}
void dij()
{
	for (int i=0;i<=n;i++) dis[i]=65000,lst[i]=0;
	cnt=0;dis[1]=0;
	priority_queue<pair<int,int> >pq;
	pq.push({0,1});
	lst[1]=-1;
	while (!pq.empty())
	{
		int x=pq.top().second;pq.pop();
		if (x==n) break;
		bg[x]=cnt;
		gt(0,lst[x],lstl[x]);
		for (int i=0;i<tot[0];i++) M[cnt++]=T[0][i];
		ed[x]=cnt;
		for (int i=fir[x];i;i=nxt[i]) if (!lst[to[i]] || (int)dis[to[i]]>(int)dis[x]+w[i])
		{
			dis[to[i]]=dis[x]+w[i];
			lst[to[i]]=x;lstl[to[i]]=w[i];
			pq.push({-1.0*dis[to[i]],to[i]});
		}
		else if (lst[to[i]] && (int)dis[to[i]]==(int)dis[x]+w[i])
		{
			if (chk(lst[to[i]],x,to[i],lstl[to[i]],w[i])) lst[to[i]]=x,lstl[to[i]]=w[i];
		}
	}
	vector<int> ans;
	int nw=n;
	while (nw!=-1) ans.push_back(nw),nw=lst[nw];
	reverse(ans.begin(),ans.end());
	cout<<ans.size()<<endl;
	for (auto p:ans) cout<<p<<' ';cout<<endl;
}
int main()
{
	int TT;cin>>TT;
	while (TT--)
	{
		int m,i;cin>>n>>m;cnt=0;TOT=0;
		for (i=1;i<=n;i++) fir[i]=0;
		for (i=1;i<=m;i++)
		{
			int u,v;cin>>u>>v;
			ust ww;cin>>ww;
			add(u,v,ww);
		}
		dij();
	}
}