#include <fstream>
#include <vector>
#include <algorithm>
#define MAXN 50005
#define INF 50000005
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct arc{
    int nod,cost;};

struct dist_nod{
    int nod,dist;};

int n,m,a,b,c,v[10*MAXN],cnt;
vector<arc> G[MAXN];
arc aux;
dist_nod df[MAXN],*first,*last,t;

bool comp(dist_nod x,dist_nod y){
    return x.dist>y.dist;}

int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>a>>b>>c;
        aux.nod=b;
        aux.cost=c;
        G[a].push_back(aux);}
    for(i=2;i<=n;i++)
        v[i]=INF;
    df[1].nod=1;
    make_heap(df+1,df+2,comp);
    first=df+1;
    last=df+2;
    while(cnt<n&&first<last){
        while((first->dist)>v[(first->nod)]){
            pop_heap(first,last,comp);
            last--;}
        t=*first;
        pop_heap(first,last,comp);
        last--;
        cnt++;
        for(i=0;i<G[t.nod].size();i++){
            aux=G[t.nod][i];
            if(t.dist+aux.cost<v[aux.nod]){
                v[aux.nod]=t.dist+aux.cost;
                last->dist=v[aux.nod];
                last->nod=aux.nod;
                push_heap(first,last,comp);
                last++;}}}
    for(i=2;i<=n;i++){
        if(v[i]<INF)
            g<<v[i]<<' ';
        else
            g<<"0 ";}
    f.close();
    g.close();
    return 0;
}