#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5 + 5;
const int MAXP = MAXN * 17;
const ll linf = 0x3f3f3f3f3f3f3f3f;

const int MX = 5e4;

int ls[MAXP], rs[MAXP], sum[MAXP], pcnt = 0;
#define lson(u) ls[u],l,mid
#define rson(u) rs[u],mid+1,r

int new_Node(int u)
{
	int v = ++pcnt;
	ls[v] = ls[u]; rs[v] = rs[u]; sum[v] = sum[u];
	return v;
}
void insert(int &u,int l,int r,int q)
{
	u = new_Node(u);
	++sum[u];
	if(l == r) return;
	int mid = (l+r)>>1;
	if(q<=mid) insert(lson(u),q);
	else insert(rson(u),q);
}
int cmp(int u,int v,int l,int r,int qu,int qv)
{
	int cu = sum[u] + (l <= qu && qu <= r);
	int cv = sum[v] + (l <= qv && qv <= r);
	if(cu == 0 || cv == 0 || l == r) return cu - cv;
	int mid = (l+r)>>1;
	int res = cmp(rs[u],rson(v),qu,qv);
	if(res == 0) res = cmp(ls[u],lson(v),qu,qv);
	return res;
}

vector<pii> g[MAXN];
ll dis[MAXN];
bool vis[MAXN];
pii pre[MAXN];
int rt[MAXN];

void solve(void)
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; ++i)
	{
		g[i].clear();
		g[i].shrink_to_fit();
	}
	for(int i=1; i<=m; ++i)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[u].emplace_back(v,w);
		g[v].emplace_back(u,w);
	}
	
	for(int i=1; i<=n; ++i)
		dis[i] = linf, vis[i] = 0;
	pcnt = 0;
	
	priority_queue< pair<ll,int> > q;
	dis[1] = 0;
	q.emplace(0, 1);
	while(q.size())
	{
		int u = q.top().second; q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		
		if(u != 1) insert(rt[u] = rt[pre[u].first], 1, MX, pre[u].second);
		
		for(auto it: g[u])
		{
			int v = it.first, w = it.second;
			if(dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				pre[v] = {u, w};
				q.emplace(-dis[v], v);
			}
			else if(dis[v] == dis[u] + w)
			{
				if(cmp(rt[pre[v].first], rt[u], 1, MX, pre[v].second, w) < 0)
					pre[v] = {u, w};
			}
		}
	}
	
	vector<int> res;
	for(int u=n; u!=1; u=pre[u].first)
		res.emplace_back(u);
	res.emplace_back(1);
	
	reverse(res.begin(), res.end());
	
	printf("%d\n",(int)res.size());
	for(auto t: res)
		printf("%d ",t);
	printf("\n");
}

int main(void)
{
//	printf("%lf\n",(sizeof(ls) * 3) / 1024.0 / 1024.0);
	
	int T;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}