rt

#include<bits/stdc++.h>
using namespace std;
const int N = 210, inf = 1e9;
int n, m, a, b, c, g[N][N], flag[N], dis[N], path[N];
void printpath(int start, int end) {
	if(path[end] == 0) printf("%d->%d", start, end);
	else {
		printpath(start, path[end]);
		printf("->%d", end);
	}
} 
int main() {
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(i == j) g[i][j] = 0;
			else g[i][j] = inf;
		}
	}
	for(int i = 1; i <= m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		g[a][b] = g[b][a] = c;
	}
	for(int i = 1; i <= n; i++) dis[i] = g[1][i];
	flag[1] = 1;
	for(int i = 1; i < n; i++) {
		int min_dis = inf, node;
		for(int j = 1; j <= n; j++) {
			if(!flag[j] && dis[j] < min_dis) {
				node = j;
				min_dis = dis[j];
			}
		}
		flag[node] = 1;
		for(int j = 1; j <= n; j++) {
			if(dis[j] > dis[node] + g[node][j]) {
				dis[j] = dis[node] + g[node][j];
				path[j] = node;
			}
		}
	}
	printf("%d\n", dis[n]);
	printpath(1, n);
	return 0;
}