#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;

#define INF 10000000

int main() {
    ifstream in("dijkstra.in");
    int n, m, edge1, edge2, cost;

    in >> n >> m;

    vector<pair<int, int> > graph[n + 1];//modif
    int distances[n + 1];//modif
    set<pair<int, int> > s;

    for (int i = 0; i < m; i++) {
        in >> edge1 >> edge2 >> cost;
        graph[edge1].push_back(pair<int, int>(cost, edge2));
    }
    in.close();

    distances[1] = 0;//modif
    for (int i = 2; i <= n; i++) {//modifc
        distances[i] = INF;
    }

    s.insert(make_pair(0, 1));//modif

    int node;
    vector<pair<int, int> >::iterator it;

    while (s.size() > 0) {
        node = (*s.begin()).second;
        cost = (*s.begin()).first;

        s.erase(*s.begin());

        for (it = graph[node].begin(); it != graph[node].end(); it++) {
            if ((*it).first + cost < distances[(*it).second]) {
                distances[(*it).second] = (*it).first + cost;
                s.insert(make_pair(distances[(*it).second], (*it).second));
            }
        }
    }
    ofstream out("dijkstra.out");
    for(int i = 2; i <= n; i++) {//modif
        if (distances[i] == INF)
            out << 0 << " ";
        else
            out << distances[i] << " ";
    }

    return 0;
}