#include <iostream>
#include<vector>
#include<queue>
using namespace std;
struct node
{
    int idx, distance;
    node () {}
    node(int _idx, int _distance) {
        idx = _idx;
        distance = _distance;
    }
    bool operator < (const node &tmp) const {
        return distance > tmp.distance;
    }
};
int main()
{
    int n, m;
    cin >> n >> m;
    vector<pair<int, int> > graph[n + 1];
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }
    bool visited[n + 1];
    int dist[n + 1];

    int parent[n + 1]; // node i ima dojdeno od parent[i]

    for(int i = 0; i <= n; i++) {
        visited[i] = false;
        dist[i] = 2e9;
        parent[i] = -1;
    }
    dist[1] = 0;
    priority_queue<node> pq;
    pq.push(node(1, 0));
    while(!pq.empty()) {
        node c = pq.top();
        pq.pop();
        visited[c.idx] = true;

        for(int i = 0; i < graph[c.idx].size(); i++) {
            int sosed = graph[c.idx][i].first;
            int d = graph[c.idx][i].second;
            if(!visited[sosed] and d + c.distance < dist[sosed]) {
                dist[sosed] = d + c.distance;
                pq.push(node(sosed, d + c.distance));
                parent[sosed] = c.idx;
            }
        }
    }

    cout << dist[n] << endl;

    int E = n;
    cout << E << " ";

    while(E != 1) {
        E = parent[E];
        cout << E << " ";
    }
    return 0;
}