#include <iostream>
#include <vector>
#include <stack>

using namespace std;

/*
 输入
 6
 9
 0 1 2
 0 2 3
 1 2 2
 1 3 4
 2 3 1
 2 4 3
 3 4 2
 3 5 7
 4 5 4
 */
int main(int argc, const char * argv[]) {
    // 一共有多少个顶点
    int n;
    cin >> n;
    
    // 初始化这个“图”
    int64_t * graph = new int64_t[n * n];
    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            graph[row * n + col] = INT64_MAX;
        }
    }
    
    // 一共有多少组边
    int p;
    cin >> p;
    for (int i = 0; i < p; i++) {
        // 依次输入每一条边
        int start, end, distance;
        cin >> start >> end >> distance;
        // 假设我们是无向图
        // 无向图具有对称性～
        graph[start * n + end] = distance;
        graph[end * n + start] = distance;
    }
    
    // 保存定点是否被访问过
    vector<bool> visited;
    visited.resize(n);
    
    // 保存源点到各点的最短距离
    vector<int64_t> distance;
    distance.resize(n);
    // 起始点到自己的距离是0～
    distance[0] = 0;
    // 其余各点都是正无穷
    for (int i = 1; i < n; i++) {
        distance[i] = INT64_MAX;
    }
    
    // 保存路径的数组
    vector<int> path;
    path.resize(n);
    
    // 从源点开始吧/
    int current = 0;
    while (true) {
        // 标记当前节点已经访问
        visited[current] = true;
        // 找出当前点可以一步访问到的所有的点
        for (int i = 0; i < n; i++) {
            if (visited[i] == false && // i 没有被访问过
                graph[current * n + i] != INT64_MAX // 并且current可以走到i这个顶点
                ) {
                // 从 0 ->...-> current -> i
                int64_t access_i_via_current = distance[current] + graph[current * n + i];
                // 从 0 ->...-> i
                int64_t access_i_via_other_path = distance[i];
                
                // 如果经过当前的点
                // 可以使得到 i 的距离变短的话
                if (access_i_via_current < access_i_via_other_path) {
                    // 那么更新路径～下面这个赋值的意思是
                    // 下标 i 这个点
                    // 应该从 current 来更近
                    path[i] = current;
                    // 更新距离
                    distance[i] = access_i_via_current;
                }
            }
        }
        
        int64_t new_minimum = INT64_MAX;
        for (int i = 0; i < n; i++) {
            // 从还没有访问过的点中
            if (visited[i] == false) {
                // 找出有着最小距离的点扩展
                if (distance[i] < new_minimum) {
                    current = i;
                    new_minimum = distance[i];
                }
            }
        }
        
        // 如果所有的点都访问过了
        // 那么这个 new_minimum 就还是初始值 +INF
        if (new_minimum == INT64_MAX) {
            // 此时就说明可以结束了
            break;
        }
    }
    
    cout << "minimum distance 0->" << n-1 << " is " << distance[n - 1] << '\n';
    
    // 保存最短路的路径
    stack<int> minimum_path;
    // 从最后一个点往回看
    current = n - 1;
    minimum_path.push(current);
    while (minimum_path.top() != 0) {
        // 从某个点到 current 是最近的
        // 把那个点放进去～
        minimum_path.push(path[current]);
        // 再来准备看是哪个点 到 那个点最近
        current = path[current];
    }
    
    // 按顺序输出整条路径
    while (!minimum_path.empty()) {
        cout << minimum_path.top() << ", ";
        minimum_path.pop();
    }
    cout << endl;
}