#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair <int, int> pii;

const int N = 1e5 + 5;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
vector < pair <int, int>> E[N];
pair <LL, int> dis[N];
bool ok[N];

struct node {
	int x;
	pair <LL, int> d;
	bool operator < (const node &a) const {
		return d > a.d;
	}
};

pair <LL, int> operator + (const pair <LL, int>& a, const pair <LL, int>& b) {
	return {a.first + b.first, a.second + b.second};
}

void work () {
	for (int i = 1; i <= n; i++) E[i].clear();
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		E[u].push_back({v, w});
		E[v].push_back({u, w});
	}
	fill(dis + 1, dis + n + 1, make_pair (INF, 0));
	dis[1] = {0ll, 0};

	{
		priority_queue <node> q;
		q.push({1, dis[1]});

		while (!q.empty()) {
			auto [x, d] = q.top(); q.pop();
			if (dis[x] != d) continue;
			for (auto [v, w] : E[x]) {
				if (dis[v] > d + make_pair((LL)w, 1)) {
					dis[v] = d + make_pair((LL)w, 1);
					q.push({v, dis[v]});
				}
			}
		}
	}
	fill(ok + 1, ok + n + 1, 0);
	{
		queue <int> q;
		ok[n] = 1;
		q.push(n);
		while (!q.empty()) {
			int x = q.front(); q.pop();
			for (auto [v, w] : E[x]) {
				if (!ok[v] && dis[x] == dis[v] + make_pair((LL)w, 1)) {
					ok[v] = 1;
					q.push(v);
				}
			}
		}
	}
	vector <int> ans = {1};
	while (ans.back() != n) {
		int x = ans.back();
		pair <int, int> best{-1, -1};
		for (auto [v, w] : E[x]) {
			if (ok[v] && dis[v] == dis[x] + make_pair((LL)w, 1)) {
				best = max(best, make_pair(w, v));
			}
		}
		ans.push_back(best.second);
	}
	printf("%d\n", (int) ans.size());
	for (auto i : ans) printf("%d ", i);
	printf("\n");
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int T = 1;
	cin >> T;
	for (int ca = 1; ca <= T; ca ++)
		work();
}