#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cassert>
#define N 100000
#define inf 1e9
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
struct reads
{
    int num,data;
    bool operator < (const reads &t)const
    {
	return data>t.data; 
    }
};
priority_queue<reads>q;
int T,n,m,tong[N+1],length,dis[N+1],dis2[N+1],p[N+1],pv[N+1];
bool used[N+1];
vector<reads>E[N+1];
vector<reads>dist[N+1];
vector<reads>operator + (vector<reads>a,int b)
{
    int ps=-1;
    vector<reads>c;
    for (int i=0;i<a.size();++i)
	if (a[i].num==b)
	{
	    a[i].data++;
	    return a;
	}
    for (int i=0;i<a.size();++i)
	if (a[i].num>b)
	    ps=i;
    for (int i=0;i<=ps;++i) c.push_back(a[i]);
    c.push_back((reads){b,1});
    for (int i=ps+1;i<a.size();++i) c.push_back(a[i]);
    return c;
}
bool operator > (vector<reads>a,vector<reads>b)
{
    for (int i=0;i<min(a.size(),b.size());++i)
	if (a[i].num!=b[i].num||a[i].data!=b[i].data)
	{
	    if (a[i].num>b[i].num||(a[i].num==b[i].num&&a[i].data>b[i].data)) return 1;
	    else return 0;
	}
    return a.size()>b.size();
}
bool cmp2(int x,int y)
{
    return dis[x]<dis[y];
}
void dijkstra()
{
    int top;
    for (int i=1;i<=n;++i) dis[i]=inf,used[i]=0;
    dis[1]=0,q.push((reads){1,0});
    while (!q.empty())
    {
	top=q.top().num,q.pop();
	if (used[top]) continue;
	used[top]=1;
	for (int i=0;i<E[top].size();++i)
	    if (dis[E[top][i].num]>dis[top]+E[top][i].data)
		dis[E[top][i].num]=dis[top]+E[top][i].data,q.push((reads){E[top][i].num,dis[E[top][i].num]});
    }
    return;
}
void dijkstra2()
{
    int top;
    for (int i=1;i<=n;++i) dis2[i]=inf,used[i]=0;
    dis2[n]=0,q.push((reads){n,0});
    while (!q.empty())
    {
	top=q.top().num,q.pop();
	if (used[top]) continue;
	used[top]=1;
	for (int i=0;i<E[top].size();++i)
	    if (dis2[E[top][i].num]>dis2[top]+E[top][i].data)
		dis2[E[top][i].num]=dis2[top]+E[top][i].data,q.push((reads){E[top][i].num,dis2[E[top][i].num]});
    }
    return;
}
int main()
{
    int x,y,z;
    T=read();
    while (T--)
    {
	n=read(),m=read(),length=0;
	for (int i=1;i<=n;++i) E[i].clear(),dist[i].clear();
	for (int i=1;i<=m;++i) x=read(),y=read(),z=read(),E[x].push_back((reads){y,z}),E[y].push_back((reads){x,z});
	dijkstra(),dijkstra2();
	for (int i=1;i<=n;++i) p[i]=i;
	sort(p+1,p+n+1,cmp2);
	for (int i=2;i<=n;++i)
	    if (dis[p[i]]+dis2[p[i]]==dis[n])
	    {
		for (int j=0;j<E[p[i]].size();++j)
		    if (dis[E[p[i]][j].num]+E[p[i]][j].data==dis[p[i]]&&dist[E[p[i]][j].num]+E[p[i]][j].data>dist[p[i]])
			dist[p[i]]=dist[E[p[i]][j].num]+E[p[i]][j].data,pv[p[i]]=E[p[i]][j].num;
		assert(1ll*dist[p[i]].size()*dist[p[i]].size()<=2*n);
	    }
	x=n,tong[++length]=n;
	while (x!=1) x=pv[x],tong[++length]=x;
	printf("%d\n",length);
	for (int i=length;i>=1;--i) printf("%d ",tong[i]);
	puts("");
    }
    return 0;
}