#include <bits/stdc++.h>
#define INF 0x3F3F3F3F
#define N 50000
using namespace std;
 
int dist[N+1];
struct heap {
    int nod, dist;
    bool operator < (const heap &x) const {return this->dist > x.dist;}
};
 
vector <heap> G[N+1];
int main () {
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");
 
    int n, m;
    fin >> n >> m;
 
    int i, j, c;
    for (; m; m--) {
        fin >> i >> j >> c;
        G[i].push_back({j, c});
    }
 
    fill(&dist[2], &dist[n+1], INF);
    priority_queue <heap> PQ;
    PQ.push({1, 0});
 
    while (!PQ.empty()) {
        auto save=PQ.top();
        PQ.pop();
 
        if (dist[save.nod] == save.dist)
            for (auto it: G[save.nod])
                if (dist[it.nod] > save.dist + it.dist)
                    dist[it.nod] = save.dist + it.dist,
                    PQ.push({it.nod, dist[it.nod]});
    }
 
    for (i=2; i<=n; ++i)
        fout << (dist[i]==INF?0:dist[i]) << ' ';
    return 0;
}