#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 101010;
const int INF = 1e9 + 10;

int n, m, d[2][MAXN];
vector<pair<int, int>> g[MAXN];

int back_mn[2][MAXN];
int back_mx[2][MAXN];
int mn[2][MAXN];
int mx[2][MAXN];
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, c; cin >> u >> v >> c;
		g[u].push_back({c, v});
		g[v].push_back({c, u});
	}
	for (int t = 0; t < 2; t++) {
		queue<int> q;
		for (int i = 1; i <= n; i++) d[t][i] = -1;
		if (t == 0) q.push(1), d[t][1] = 0;
		else q.push(n), d[t][n] = 0;
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			for (auto [w, x] : g[v]) {
				if (d[t][x] == -1) {
					d[t][x] = d[t][v] + 1;
					q.push(x);
				}
			}
		}
	}
	int D = d[0][n];
	// cout << "distance " << D << "?\n";
	for (int t = 0; t < 2; t++) {
		for (int i = 1; i <= n; i++) mn[t][i] = INF;
		for (int i = 1; i <= n; i++) mx[t][i] = -1;
	}
	for (int t = 0; t < 2; t++) {
		queue<int> q;
		if (t == 0) q.push(1);
		else q.push(n);

		while (!q.empty()) {
			int v = q.front();
			q.pop();
			for (auto [w, x] : g[v]) {
				if (d[t][x] == d[t][v] + 1 && d[t][v] + d[t ^ 1][x] + 1 == D) { // need to check?
					if (mn[t][x] > min(mn[t][v], w)) {
						mn[t][x] = min(mn[t][v], w);
						back_mn[t][x] = v;
					}
					if (mx[t][x] < max(mx[t][v], w)) {
						mx[t][x] = max(mx[t][v], w);
						back_mx[t][x] = v;
					}
					q.push(x);
				}
			}
		}
	}
	// for (int i = 1; i <= n; i++) {
	// 	cout << mn[0][i] << ' ' << mx[0][i] << "?\n";
	// }
	int cs = 1;
	int vn = 1;
	int val = 0;
	for (int i = 2; i < n; i++) {
		if (d[0][i] + d[1][i] != D) continue;
		// case 1 : min first
		if (val < mx[1][i] - mn[0][i]) {
			val = mx[1][i] - mn[0][i];
			vn = i;
			cs = 1;
		}
		// case 2 : max first
		if (val < mx[0][i] - mn[1][i]) {
			val = mx[0][i] - mn[1][i];
			vn = i;
			cs = 2;
		}
	}
	vector<int> pre, suf;
	if (cs == 1) {
		for (int v = vn; v != 1; v = back_mn[0][v]) {
			assert(1 <= v && v <= n);
			pre.push_back(v);
		}
		pre.push_back(1);
		for (int v = vn; v != n; v = back_mx[1][v]) {
			assert(1 <= v && v <= n);
			if (v != vn) suf.push_back(v);
		}
		suf.push_back(n);
	}
	else {
		for (int v = vn; v != 1; v = back_mx[0][v]) {
			assert(1 <= v && v <= n);
			pre.push_back(v);
		}
		pre.push_back(1);
		for (int v = vn; v != n; v = back_mn[1][v]) {
			assert(1 <= v && v <= n);
			if (v != vn) suf.push_back(v);
		}
		suf.push_back(n);
	}
	reverse(pre.begin(), pre.end());
	for (int x : suf) pre.push_back(x);

	cout << (int)pre.size() - 1 << '\n';
	for (int x : pre) cout << x << ' ';
	cout << '\n';
}