#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>

#define INF 0x3F3F3F3F
#define N 50000

using namespace std;
using namespace __gnu_pbds;

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;}

    heap *urm;
} *G[N+1];

typedef __gnu_pbds::priority_queue <heap> myheap;
void add (heap* &p, int x, int y) {
    heap *e = new heap(x, y);
    e->urm = p;
    p = e;
}

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;
        add(G[i], j, c);
    }

    myheap PQ;
    fill(&dist[2], &dist[n+1], INF);
    PQ.push({1, 0});

    while (!PQ.empty()) {
        auto save=PQ.top();
        PQ.pop();

        if (dist[save.nod] == save.dist)
            for (heap *it = G[save.nod]; it; it=it->urm)
                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;
}