#include<fstream>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define FOR(a,b,c) for (int a=b;a<=c;++a)
#define Nmax 50100
#define inf 50100100

int N,M;
int d[Nmax];

struct elem {
    int y,dist;
};
vector<elem> v[Nmax];
priority_queue<elem> heap;

bool operator <(elem a,elem b) {
    return a.dist>b.dist;
}

int main() {
    f>>N>>M;
    FOR (i,1,M) {
        int x,y,d;
        f>>x>>y>>d;
        elem A;
        A.y=y;
        A.dist=d;
        v[x].push_back(A);
    }
    FOR (i,2,N) {
        d[i]=inf;
    }
    elem A;
    A.y=1;
    A.dist=-1;
    heap.push(A);
    while (!heap.empty()) {
        elem A=heap.top();
        heap.pop();
        if (d[A.y]<A.dist) {
            continue;
        }
        vector<elem>::iterator it;
        int nod=A.y;
        for (it=v[nod].begin();it<v[nod].end();++it) {
            int vecin=(*it).y;
            if (d[vecin]>d[nod]+(*it).dist) {
                d[vecin]=d[nod]+(*it).dist;
                elem B;
                B.y=vecin;
                B.dist=d[vecin];
                heap.push(B);
            }
        }
    }
    FOR (i,2,N) {
        if (d[i]==inf) {
            g<<"0 ";
        }
        else {
            g<<d[i]<<' ';
        }
    }
    f.close();g.close();
    return 0;
}