#include <stdio.h>

using namespace std;
FILE *in,*out;

int n,m,k=0;
int d[50002],start[50002],h[50002],pos[50002];

struct{
    int node,cost,next;
}v[250002];

void read(){
    int k=0,a,b,c;
    fscanf(in,"%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        fscanf(in,"%d %d %d",&a,&b,&c);
        v[++k].node=b,v[k].cost=c,v[k].next=start[a],start[a]=k;
    }
}

void swap_h(int x, int y){
    int aux=h[x];
    h[x]=h[y],h[y]=aux;
}

void sift(int node){
    int son;
    while(node<=k){
        son=0;
        if(node*2<=k){
            son=node*2;
            if(node*2+1<=k && d[h[node*2]]>d[h[node*2+1]])
                son=node*2+1;
        }
        else return;

        if(d[h[node]]>d[h[son]]){
            pos[h[node]]=son;
            pos[h[son]]=node;
            swap_h(node,son);
            node=son;
        }
        else return;
    }
}

void percolate(int node){
    int fat;
    while(h[node/2]>h[node] && node>1){
        pos[node/2]=node;
        pos[node]=node/2;
        swap_h(node/2,node);
        node=node/2;
    }
}

void dijkstra(){
    for(int i=2;i<=n;i++)
        d[i]=999999999,pos[i]=-1;
    pos[1]=1;
    h[k=1]=1;
    while(k){
        int mi=h[1];
        swap_h(k,1);
        pos[h[1]]=1;
        k--;
        sift(1);
        for(int i=start[mi];i;i=v[i].next)
            if(d[v[i].node]>v[i].cost+d[mi]){
                d[v[i].node]=v[i].cost+d[mi];
                if(pos[v[i].node]!=-1)
                    percolate(pos[v[i].node]);
                else{
                    h[++k]=v[i].node;
                    pos[v[i].node]=k;
                    percolate(k);
                }
            }
    }
}

int main(){
    in=fopen("dijkstra.in","r");
    out=fopen("dijkstra.out","w");
    read();
    dijkstra();
    for(int i=2;i<=n;i++)
        fprintf(out,"%d ",d[i]);
    return 0;
}