#include<bits/stdc++.h>
#define ll long long
#define ust unsigned short
#define fi first
#define sc second
using namespace std;
pair<ust,ust> M[12000000];
int cnt;
ust dis[100002];
int lst[100002],n,bg[100002],ed[100002];
ust lstl[100002];
vector<pair<int,ust> > e[100002];
pair<ust,ust> T[2][100002];int tot[2];
void gt(pair<ust,ust> *tmp,int x,ust o,int &tot)
{
	tot=0;
	for (int i=bg[x];i<ed[x];i++) if (M[i].fi>o)
	{
		tmp[tot++]=M[i];
	}
	else if (M[i].fi==o)
	{
		tmp[tot]=M[i];tmp[tot++].sc++;
	}else
	{
		if (cnt==bg[x] || M[cnt-1].fi>o)
		{
			tmp[tot++]={o,1};
		}
		tmp[tot++]=M[i];
	}
}
int chk(int x,int y,int z,ust ox,ust oy)
{
	gt(T[0],x,ox,tot[0]);
	gt(T[1],y,oy,tot[1]);
	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(T[0],lst[x],lstl[x],tot[0]);
		for (int i=0;i<tot[0];i++) M[cnt++]=T[0][i];
		ed[x]=cnt;
		for (auto p:e[x]) if (!lst[p.fi] || (int)dis[p.fi]>(int)dis[x]+p.sc)
		{
			dis[p.fi]=dis[x]+p.sc;
			lst[p.fi]=x;lstl[p.fi]=p.sc;
			pq.push({-1.0*dis[p.fi],p.fi});
		}
		else if (lst[p.fi] && (int)dis[p.fi]==(int)dis[x]+p.sc)
		{
			if (chk(lst[p.fi],x,p.fi,lstl[p.fi],p.sc)) lst[p.fi]=x,lstl[p.fi]=p.sc;
		}
	}
	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;
		for (i=1;i<=n;i++) e[i].clear();
		for (i=1;i<=m;i++)
		{
			int u,v;cin>>u>>v;
			ust w;cin>>w;
			e[u].push_back({v,w});
			e[v].push_back({u,w});
		}
		dij();
	}
}