#include <bits/stdc++.h>
#define INF 0x3F3F3F3F
#define N 50000
using namespace std;

int dist[N+1];
class heap {
public:
    int nod, dist;
    heap (int i, int j) {tie(nod, dist)=tie(i, j);}
    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;
}