#include <stdio.h>
#include <vector>
#define fr(i,a,b) for(int i=a;i<b;++i)
#define N 50000
#define M 250000
using namespace std;
struct edge{
    int v,d;
    edge(int _v,int _d){v=_v;d=_d;}
    };
vector<edge>o[N];

int dist[N];
int p[N],pb[N],s;

void sw(int i,int j){
    int t=dist[i];
    dist[i]=dist[j];
    dist[j]=t;
    p[pb[i]]=j;
    p[pb[j]]=i;
    t=pb[i];
    pb[i]=pb[j];
    pb[j]=t;
    }

void heap(int i){
    while(i<=s/2){
        int l=i<<1,r=l+1;
        int m=i;
        if(l<s&&dist[l]!=-1&&(dist[i]==-1||dist[l]<dist[i]))m=l;
        if(r<s&&dist[r]!=-1&&(dist[m]==-1||dist[r]<dist[m]))m=r;
        if(m==i)return;
        sw(i,m);
        i=m;
        }
    }

int pop(){
    int r=pb[0];
    sw(0,s-1);
    --s;
    heap(0);
    return r;
    }

void print();

int upd(int i,int x){
    int pi=p[i];
    if(dist[pi]!=-1&&dist[pi]<=x)return 0;
    int r=dist[pi]==-1;
    dist[pi]=x;
    while(pi&&(dist[pi>>1]==-1||dist[pi]<dist[pi>>1])){
        sw(pi,pi>>1);
        pi=pi>>1;
        }
    return r;
    }

int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n,m,x,y,z;
    scanf("%i%i",&n,&m);
    fr(i,0,m){
        scanf("%i%i%i",&x,&y,&z);
        o[x-1].push_back(edge(y-1,z));
        }
    dist[0]=0;
    fr(i,1,n)dist[i]=-1,p[i]=pb[i]=i;
    s=n;
    int grey=1;
    while(grey){
        int m=pop();
        int sz=(int)o[m].size();
        fr(i,0,sz)grey+=upd(o[m][i].v,dist[p[m]]+o[m][i].d);
        --grey;
        }
    fr(i,1,n)printf("%i ",dist[p[i]]==-1?0:dist[p[i]]);
    return 0;
    }