#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const int M = 2e5 + 10;

struct edge{int from, to, c;}eg[M << 1];
int front[N], num;
void add(int x, int y, int c){eg[++ num] = (edge){front[x], y, c}; front[x] = num;}


int dis[N][2], maxs[N][2], mins[N][2];
int n, m;

void init(){for (int i = 1; i <= n; ++ i) dis[i][0] = dis[i][1] = 1e9;}

int ans;
deque<int>v;

void bfs(int s, int t){
	queue<int>q;
	
	init(); for (int i = 1; i <= n; ++ i) maxs[i][0] = -1, maxs[i][1] = 0;
	dis[s][0] = 0, q.push(s);
	while(!q.empty()){
		int o = q.front();
		q.pop();
		for (int i = front[o]; i; i = eg[i].from){
			int to = eg[i].to;
			if(dis[o][0] + 1 == dis[to][0] && maxs[to][0] < max(maxs[o][0], eg[i].c)) maxs[to][0] = max(maxs[o][0], eg[i].c), maxs[to][1] = o;
			if(dis[o][0] + 1 < dis[to][0]){
				dis[to][0] = dis[o][0] + 1;
				maxs[to][0] = max(maxs[o][0], eg[i].c), maxs[to][1] = o;
				q.push(to);
			}
		}
	}
	
	for (int i = 1; i <= n; ++ i) mins[i][0] = 1e9, mins[i][1] = 0;
	dis[t][1] = 0, q.push(t);
	while(!q.empty()){
		int o = q.front();
		q.pop();
		for (int i = front[o]; i; i = eg[i].from){
			int to = eg[i].to;
			if(dis[o][1] + 1 == dis[to][1] && mins[to][0] < min(mins[o][0], eg[i].c)) mins[to][0] = min(mins[o][0], eg[i].c), mins[to][1] = o;
			if(dis[o][1] + 1 < dis[to][1]){
				dis[to][1] = dis[o][1] + 1;
				mins[to][0] = min(mins[o][0], eg[i].c), mins[to][1] = o;
				q.push(to);
			}
		}
	}
	
	for (int i = 2; i < n; ++ i){
		if(dis[i][0] + dis[i][1] == dis[t][0] && ans < maxs[i][0] - mins[i][0]){
			ans = maxs[i][0] - mins[i][0];
			v.clear();
			v.push_back(i);
			for (int o = maxs[i][1]; o; o = maxs[o][1]) v.push_front(o);
			for (int o = mins[i][1]; o; o = mins[o][1]) v.push_back(o);
		}
	}
}

void solve(){
	num = 0;
	for (int i = 1; i <= n; ++ i) front[i] = 0;
	cin >> n >> m;
	ans = -1;
	for (int i = 1; i <= m; ++ i){
		int x, y, c; cin >> x >> y >> c;
		add(x, y, c); add(y, x, c);
		if(min(x, y) == 1 && max(x, y) == n) ans = 0, v.push_back(1), v.push_back(n);
	}
	
	bfs(1, n); bfs(n, 1);
	if(v[0] != 1) reverse(v.begin(), v.end());
	cout << v.size() - 1 << "\n";
	for (int o:v) cout << o << " ";
	cout << "\n";
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T = 1;
	while(T --) solve();
}