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

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

vector<arc> node[123456];
vector<int> clr[123456];
int n, dis[123456], path[123456], min_point;


void bfs() {
	queue<int> q,p;
	q.push(1);
	dis[1] = 0;
	int ok = 1;
	while (!q.empty()) {
		int f = q.front(); q.pop();
		if (!ok && dis[f] != dis[p.front()])break;
		for (int i = 0; i < node[f].size(); i++) {
			if (dis[node[f][i].v] != -1) {
				if (path[node[f][i].v] == f) {
					if (clr[node[f][i].v].back() > node[f][i].c)clr[node[f][i].v].back() = node[f][i].c;
				}
				continue;
			}
			if (node[f][i].v == n) {
				clr[f].push_back(node[f][i].c);
				p.push(f);
				ok = 0;
			}
			if (ok) {
				clr[node[f][i].v] = clr[f];
				clr[node[f][i].v].push_back(node[f][i].c);
				dis[node[f][i].v] = dis[f] + 1;
				path[node[f][i].v] = f;
				q.push(node[f][i].v);
			}
		}
	}
	min_point = p.front(); p.pop();
	while (!p.empty()) {
		int ff = p.front(); p.pop();
		for (int i = 0; i <= dis[ff]; i++) {
			if (clr[ff][i] > clr[min_point][i]) { break; }
			if (clr[ff][i] < clr[min_point][i]) { min_point = ff; break; }
		}
	}
}
int main() {
	int m;
	while (cin >> n >> m) {
		memset(dis, -1, sizeof(dis));
		memset(path, 0, sizeof(path));
		while (m--) {
			int a, b, c;
			cin >> a >> b >> c;
			node[a].push_back(arc(b, c));
			node[b].push_back(arc(a, c));
		}
		bfs();
		for (int i = 1; i <= n;i++) {
			node[i].clear();
		}
		cout << dis[min_point] + 1 << endl;
		for (int i = 0; i < dis[min_point]; i++) {
			cout << clr[min_point][i] << ' ';
		}
		cout << clr[min_point][dis[min_point]] << endl;
		for (int i = 1; i <= n; i++) {
			clr[i].clear();
		}
	}
	return 0;
}

我换了个方法，我就用一次bfs，怎么又爆了，求助求助