#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

typedef struct list {
	int v, c;
	list(int v, int c) :v(v), c(c) {}
}list;

vector<list> node[100005];
int n, dis[100005], clrr[100005], path[100005][2], num = 0;;

void bfsn() {
	queue<int> q;
	q.push(n);
	dis[n] = 0;
	while (!q.empty()) {
		int f = q.front(); q.pop();
		for (int i = 0; i < node[f].size(); i++) {
			if (dis[node[f][i].v] != -1)continue;
			dis[node[f][i].v] = dis[f] + 1;
			q.push(node[f][i].v);
		}
	}
}

void bfs1() {
	queue<int> q;
	q.push(1);
	path[1][0] = 0;
	while (!q.empty()) {
		queue<int> p = q;
		while (!q.empty()) {
			int f = q.front(); q.pop();
			for (int i = 0; i < node[f].size(); i++) {
				if (dis[node[f][i].v] != dis[f] - 1)continue;
				if (node[f][i].c < clrr[dis[node[f][i].v]])clrr[dis[node[f][i].v]] = node[f][i].c;
			}
		}
		while (!p.empty()) {
			int f = p.front(); p.pop();
			for (int i = 0; i < node[f].size(); i++) {
				if (dis[node[f][i].v] != dis[f] - 1)continue;
				if (node[f][i].c == clrr[dis[node[f][i].v]]) {
					q.push(node[f][i].v);
					path[node[f][i].v][0] = f;
					path[node[f][i].v][1] = clrr[dis[node[f][i].v]];
				}
			}
		}
	}
}

int main() {
	int m;
	while (cin >> n >> m) {
		int mm = m;
		memset(dis, -1, sizeof(dis));
		memset(path, 0, sizeof(path));
		while (mm--) {
			int u, v, c;
			cin >> u >> v >> c;
			node[u].push_back(list(v, c));
			node[v].push_back(list(u, c));
		}
		bfsn();
		for (int i = 0; i < dis[1]; i++) {
			clrr[i] = 1000000000;
		}
		cout << dis[1] << endl;
		bfs1();
		for (int i = 1; i <= n; i++) {
			node[i].clear();
		}
		for (int i = dis[1] - 1; i > 0; i--) {
			cout << clrr[i] << ' ';
		}
		cout << clrr[0] << endl;
	}
	return 0;
}

有没有什么优化的机会啊兄弟们