#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int mo=998244353;
struct node{
	int son[2],hash;
}tr[2000010];
int t,n,m,vis[100010],pre[100010],root[100010],tot,two[100010],maxd;
int dis[100010],res;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > q;
vector<pair<int,int> > edge[100010];
void getans(int x){
	if (!x){
		printf("%d\n",res);
		return;
	}
	res++;
	getans(pre[x]);
	printf("%d ",x);
}
int newnode(){
	++tot;
	tr[tot].son[0]=tr[tot].son[1]=tr[tot].hash=0;
	return tot;
}
void ins(int pwh,int wh,int l,int r,int x){
	if (l==r){
		tr[wh].hash=tr[pwh].hash+1;
		return;
	}
	int mid=(l+r)/2;
	if (x<=mid){
		tr[wh].son[0]=newnode();
		tr[wh].son[1]=tr[pwh].son[1];
		ins(tr[pwh].son[0],tr[wh].son[0],l,mid,x);
	}
	else{
		tr[wh].son[1]=newnode();
		tr[wh].son[0]=tr[pwh].son[0];
		ins(tr[pwh].son[1],tr[wh].son[1],mid+1,r,x);
	}
	tr[wh].hash=(1ll*tr[tr[wh].son[1]].hash*two[mid-l+1]+tr[tr[wh].son[0]].hash)%mo;
}
int comp(int wh,int pwh,int l,int r,int a,int b){
	if (l==r) return tr[wh].hash+(a==l)>tr[pwh].hash+(b==l);
	int mid=(l+r)/2;
	int lh=tr[tr[wh].son[1]].hash;
	int rh=tr[tr[pwh].son[1]].hash;
	if (a>mid&&a<=r) lh=(lh+two[a-mid])%mo;
	if (b>mid&&b<=r) rh=(rh+two[b-mid])%mo;
	if (lh!=rh) return comp(tr[wh].son[1],tr[pwh].son[1],mid+1,r,a,b);
	return comp(tr[wh].son[0],tr[pwh].son[0],l,mid,a,b);
}
int main(){
	//freopen("H.in","r",stdin);
	scanf("%d",&t);
	two[0]=1;
	for (int i=1;i<=100000;i++) two[i]=two[i-1]*100003%mo;
	while (t--){
		tot=0;
		scanf("%d%d",&n,&m);
		for (int i=0;i<m;i++){
			int o,p,t;
			scanf("%d%d%d",&o,&p,&t);
			edge[o].pb(mp(p,t));
			edge[p].pb(mp(o,t));
			maxd=max(maxd,t);
		}
		for (int i=2;i<=n;i++) dis[i]=100000;
		q.push(mp(0,1));
		while (!q.empty()){
			int now=q.top().se;
			if (!vis[now]){
				root[now]=newnode();
				if (now!=1) ins(root[pre[now]],root[now],1,maxd,dis[now]-dis[pre[now]]);
				for (int i=0;i<edge[now].size();i++)
				if (dis[edge[now][i].fi]>dis[now]+edge[now][i].se){
					dis[edge[now][i].fi]=dis[now]+edge[now][i].se;
					pre[edge[now][i].fi]=now;
					q.push(mp(dis[edge[now][i].fi],edge[now][i].fi));
				}
				else if (dis[edge[now][i].fi]==dis[now]+edge[now][i].se&&comp(root[now],root[pre[edge[now][i].fi]],1,maxd,edge[now][i].se,dis[edge[now][i].fi]-dis[pre[edge[now][i].fi]])==1) pre[edge[now][i].fi]=now;
				vis[now]=1;
			}
			q.pop();
		}
		res=0;
		getans(n);
		printf("\n");
		for (int i=1;i<=n;i++) edge[i].clear(),vis[i]=0;
	}
}