#include <bits/stdc++.h>
#define MINint -2000000000
#define LEN 1000000

std::priority_queue< std::pair<int,int> > h;

std::vector<int> v[50000][2];

char BUFF[LEN];

FILE*fi;

int k=0;

int cit(){
    int nr=0;
    while(BUFF[k]<'0' || BUFF[k]>'9'){
        if(++k==LEN){
            fread(BUFF,1,LEN,fi);
            k=0;
        }
    }
    while(BUFF[k]>='0' && BUFF[k]<='9'){
        nr=nr*10+BUFF[k]-'0';
        if(++k==LEN){
            fread(BUFF,1,LEN,fi);
            k=0;
        }
    }
    return nr;
}

int best[50000];

void reset(int n){
    for(int i=0;i<n;i++){
        best[i]=MINint;
    }
}

int main()
{
    int n,m,i,a,b,c,nod,val,nod2,val2;
    FILE*fo;
    fi=fopen("dijkstra.in","r");
    fo=fopen("dijkstra.out","w");
    fread(BUFF,1,LEN,fi);
    n=cit();
    m=cit();
    for(i=0;i<m;i++){
        a=cit();
        b=cit();
        c=cit();
        a--;
        b--;
        c=-c;
        v[a][0].push_back(b);
        v[a][1].push_back(c);
    }
    reset(n);
    h.push({0,0});
    best[0]=0;
    while(h.empty()!=1){
        nod=h.top().second;
        val=h.top().first;
        h.pop();
        if(best[nod]==val){
            for(i=0;i<v[nod][0].size();i++){
                nod2=v[nod][0][i];
                val2=v[nod][1][i]+val;
                if(best[nod2]<val2){
                    best[nod2]=val2;
                    h.push({val2,nod2});
                }
            }
        }
    }
    for(i=1;i<n;i++){
        if(best[i]==MINint)
            fprintf(fo,"0 ");
        else fprintf(fo,"%d ",-best[i]);
    }
    fclose(fi);
    fclose(fo);
    return 0;
}