#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>

#define MAXN 50001

#define Inf numeric_limits<int>::max()

using namespace std;
using Graph = vector<vector<pair<int, int> > >;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

vector<int> distances(MAXN, Inf);
int N, M;

vector<int> nextHop(MAXN, Inf);

struct Comparator 
{
    bool operator() (const int& x, const int& y) const
    {
        return distances[x] > distances[y];
    }
};

void find_min_road(Graph& G, int source)
{
    priority_queue<int, vector<int>, Comparator> Q;
    
    Q.push(source);
    distances[source] = 0;

    while (Q.size()) {
        int currNode = Q.top();
        Q.pop();

        for (auto &node : G[currNode]) {
            if (distances[currNode] + node.second < distances[node.first]) {
                distances[node.first] = distances[currNode] + node.second;
                Q.push(node.first);
                nextHop[currNode] = node.first;
            } else if (distances[currNode] + node.second == distances[node.first]) {
                if (node.first < nextHop[currNode])
                    nextHop[currNode] = node.first;
            }
        }
    }
}

int main()
{
    in >> N >> M;

    Graph G(N + 1);
    int x, y, c;
    for (int i = 1; i <= M; i++) {
        in >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
        G[y].push_back(make_pair(x, c));
    }

    find_min_road(G, 1);

    for (int i = 2; i <= N; i++)
        (distances[i] == Inf) ? out << "0 " : out << distances[i] << " ";

    out << '\n';

    out << "nextHop[1]: " << nextHop[1] << '\n';
    out << "nextHop[3]: " << nextHop[3] << '\n';

    return 0;
}