#include<bits/stdc++.h>
#define rep(i,a,b) for (int i = (a); i <= (b); ++i)
#define drep(i,a,b) for (int i = (a); i >= (b); --i)
#define grep(i,u) for (int i = head[u],v = e[i].v; i; v = e[i = e[i].nxt].v)
#define LL long long
#define il inline
#define pii pair<int,int>
#define pll pair<LL,LL>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
il LL read() {
	LL x = 0,y = 1; char ch = getchar(); while (!isdigit(ch)) {if (ch == '-') y = -y; ch = getchar();}
	while (isdigit(ch)) {x = x*10+ch-'0'; ch = getchar();} return x*y;
}
namespace qiqi {
	const int N = 1e5+5,M = 3e5+5,L = 27,P = 1e9+7; const LL INF = 0x3f3f3f3f3f3f3f3f;
	int n,m,ecnt,head[N],cnt,pw[N],rt[N],pool[N*L],tp,pre[N],pos[N]; LL dis[N]; pll p[N]; bool vis[N];
	struct Edge {int v,w,nxt;} e[M<<1]; il void add(int u,int v,int w) {e[++ecnt] = (Edge){v,w,head[u]}; head[u] = ecnt;}
	il void Dij(int s) {
		rep(i,1,n) {dis[i] = INF; vis[i] = 0;}
		priority_queue<pll> q; q.push(mp(dis[s] = 0,s));
		while (!q.empty()) {
			int u = q.top().se; q.pop();
			if (vis[u]) continue; vis[u] = 1;
			grep(i,u) if (dis[u]+e[i].w < dis[v]) {
				q.push(mp(-(dis[v] = dis[u]+e[i].w),v));
			}
		}
	}
	struct Node {int lc,rc,h,siz;} a[N*L];
	il int new_node() {
		int x = tp ? pool[tp--] : ++cnt;
		a[x] = (Node){0,0,0,0}; return x;
	}
	il void init(int n) {
		pw[0] = 1; rep(i,1,n) pw[i] = 1LL*N*pw[i-1]%P;
	}
	il void push_up(int x,int l,int r) {
		int mid = l+((r-l)>>1); a[x].siz = a[a[x].lc].siz+a[a[x].rc].siz;
		a[x].h = (1LL*a[a[x].lc].h*pw[r-mid]%P+a[a[x].rc].h)%P;
	}
	void upd(int &x,int y,int l,int r,int p) {
		a[x = new_node()] = a[y]; if (l == r) {++a[x].h; ++a[x].siz; return;} int mid = l+((r-l)>>1);
		p <= mid ? upd(a[x].lc,a[y].lc,l,mid,p) : upd(a[x].rc,a[y].rc,mid+1,r,p); push_up(x,l,r);
	}
	void del(int x,int l,int r,int p) {
		if (!x) return; pool[++tp] = x; if (l == r) return; int mid = l+((r-l)>>1);
		p <= mid ? del(a[x].lc,l,mid,p) : del(a[x].rc,mid+1,r,p);
	}
	bool qry(int x,int y,int l,int r) {
		if (l == r) return a[x].h > a[y].h; int mid = l+((r-l)>>1);
		return a[a[x].lc].siz != a[a[x].rc].siz || a[a[x].rc].h != a[a[y].rc].h ? qry(a[x].rc,a[y].rc,mid+1,r) : qry(a[x].lc,a[y].lc,l,mid);
	}
	il void print(int x,int c) {
		if (!x) {
			printf("%d\n",c); return;
		}
		print(pre[x],c+1);
		printf("%d ",x);
		if (!c) puts("");
	}
	void main() {
		ecnt = cnt = tp = 0; n = read(); m = read();
		rep(i,1,n) head[i] = rt[i] = 0;
		rep(i,1,m) {
			int u = read(),v = read(),w = read();
			add(u,v,w); add(v,u,w);
		}
		Dij(1); rep(i,1,n) p[i] = mp(dis[i],i);
		sort(p+1,p+n+1);
		rep(i,1,n) {
			int u = p[i].se;
			grep(i,u) if (dis[u]+e[i].w == dis[v]) {
				int x; upd(x,rt[u],1,n,e[i].w);
				if (!rt[v] || qry(x,rt[v],1,n)) {
					del(rt[v],1,n,pos[v]); rt[v] = x;
					pre[v] = u; pos[v] = e[i].w;
				}
				else {
					del(x,1,n,e[i].w);
				}
			}
		}
		print(n,0);
	}
}
int main() {
	qiqi::init(1e5); int T = read(); while (T--) qiqi::main(); return 0;
}