#include <bits/stdc++.h>
   
using namespace std;
 
typedef long long int ll;
typedef long double ld;

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

const int INF = 1e9;

vector < vector < pair < int, int > > > G;

vector < int > Dijkstra(int startNode, int n) {
    vector < int > dist(n, INF);
    dist[startNode] = 0;

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

    while (!PQ.empty()) {
        int node = PQ.top().second;
        int cost = PQ.top().first;
        PQ.pop();

        if (cost != dist[node]) continue;

        for (auto x: G[node]) {
            if (cost + x.second < dist[x.first]) {
                dist[x.first] = cost + x.second;
                PQ.push({dist[x.first], x.first});
            }
        }
    }

    return dist;
}

int main() {
    
    int n, m; fin >> n >> m;

    G.resize(n);
    for (int i = 0; i < m; ++i) {
        int a, b, cost; fin >> a >> b >> cost;

        G[a - 1].push_back({b - 1, cost});
    }

    vector < int > dist = Dijkstra(0, n);
    for (int i = 1; i < n; ++i) {
        if (dist[i] == INF) {
            fout << "0 ";
        } else {
            fout << dist[i] << " ";
        }
    }
    return 0;
}