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

#define INF (1 << 30)

struct weighted_node {
    int to;
    int cost;
};

int main() {
    ifstream fin("dijkstra.in");

    int n, m;
    fin >> n >> m;
    vector<vector<weighted_node>> graf(n+1); 
    vector<int> dist(n+1, INF);

    int current;
    weighted_node temp;
    for (size_t i = 0; i < m; ++i) {
        fin >> current >> temp.to >> temp.cost;
        graf[current].push_back(temp);
    }

    fin.close();

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 1}); 

    dist[1] = 0;
    while (!pq.empty()) {
        int dist_cur = pq.top().first;
        int nod = pq.top().second;
        pq.pop();

        if (dist_cur > dist[nod]) continue;

        for (const auto& edge : graf[nod]) {
            int to = edge.to;
            int cost = edge.cost;

            if (dist[to] > dist[nod] + cost) {
                dist[to] = dist[nod] + cost;
                pq.push({dist[to], to});
            }
        }
    }

    ofstream fout("dijkstra.out");
    for (int i = 2; i <= n; ++i) {
        fout << (dist[i] == INF ? 0 : dist[i]) << " ";
    }
    fout << "\n";
    fout.close();

    return 0;
}