#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[2] = {1e9+7,1e9+9}; const LL INF = 0x3f3f3f3f3f3f3f3f;
	int n,m,ecnt,head[N],cnt,pw[2][N],rt[N],pool[N*L],tp,pre[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[2];} 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) {
		rep(j,0,1) {
			pw[j][0] = 1; rep(i,1,n) pw[j][i] = 1LL*N*pw[j][i-1]%P[j];
		}
	}
	il void push_up(int x,int l,int r) {
		int mid = l+((r-l)>>1);
		rep(i,0,1) a[x].h[i] = (1LL*a[a[x].lc].h[i]*pw[i][r-mid]%P[i]+a[a[x].rc].h[i])%P[i];
	}
	void upd(int &x,int y,int l,int r,int p) {
		a[x = ++cnt] = a[y]; if (l == r) {rep(i,0,1) ++a[x].h[i]; 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) {
		if (!x) return; pool[++tp] = x;
		a[x].lc > x ? del(a[x].lc) : del(a[x].rc);
	}
	bool qry(int x,int y,int l,int r) {
		if (l == r) return a[x].h[0] > a[y].h[0]; int mid = l+((r-l)>>1);
		return a[a[x].rc].h[0] != a[a[y].rc].h[0] || a[a[x].rc].h[1] != a[a[y].rc].h[1] ? 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]); rt[v] = x; pre[v] = u;
				}
				else {
					del(x);
				}
			}
		}
		print(n,0);
	}
}
int main() {
	qiqi::init(1e5); int T = read(); while (T--) qiqi::main(); return 0;
}

answer.code:19:65: error: narrowing conversion of ‘1.000000007e+9’ from ‘double’ to ‘int’ [-Wnarrowing]
   19 |         const int N = 1e5+5,M = 3e5+5,L = 27,P[2] = {1e9+7,1e9+9}; const LL INF = 0x3f3f3f3f3f3f3f3f;
      |                                                                 ^
answer.code:19:65: error: narrowing conversion of ‘1.000000009e+9’ from ‘double’ to ‘int’ [-Wnarrowing]