#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

const pair<int,vector<int>>& min(const pair<int,vector<int>>& a, const pair<int,vector<int>>& b) {
  return (a.first < b.first) ? a : b;     // or: return !comp(b,a)?a:b; for version (2)
}

pair<int,vector<int>> findShortestPath(vector<vector<int>>& graph, int v){
	vector<pair<int,vector<int>>> childs;
	for (int i=0; i<v; i++){
		if (graph[i][v] != -1){
			pair<int,vector<int>> path = findShortestPath(graph,i);
			path.second.push_back(v+1);
			childs.push_back(make_pair(path.first + graph[i][v], path.second));
		}
	}
	if (childs.size() == 2){
		pair<int,vector<int>> path = min(childs[0],childs[1]);
		return make_pair(path.first*2+1, path.second);
	}
	if (childs.size() == 1){
		return make_pair(childs[0].first,childs[0].second);
	}
	else{
		vector<int> start = {v+1};
		return make_pair(0,start);
	}
}

int main()
{
	int n, e;
	cin >> n; //num of vertices
	cin >> e; //num of queues
	vector<vector<int>> graph;
	
	//initialize graph matrix cells to -1
	graph.resize(n);
	for (int i=0;i<n;i++){
		graph[i].resize(n);
		for (int j=0;j<n;j++)
			graph[i][j] = -1;
	}
	
	//add edges and their weights
	for (int i=0;i<e;i++){
		int s,d,val;
		cin >> s >> d >> val;
		graph[s-1][d-1] = val;
	}
	
	//run algorithm
	pair<int,vector<int>> path = findShortestPath(graph, n-1);
	
	//print results
    cout << path.first << endl;
    for (int i=0;i<path.second.size()-1;i++)
    	cout << path.second[i] << " -> ";
    cout << path.second[path.second.size()-1] << endl;
    
    return 0;
}