#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

#define BUF_SIZE 16384
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline int nextnum(){
    int a=0;
    char c=nextch();
    while(c<'0' || c>'9')
        c=nextch();
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a;
}

#define MAXN 50000
#define MAXM 250000
int heap[MAXN+1], poz[MAXN+1], luat[MAXN+1];
int list[MAXN+1], val[MAXM+1], cost[MAXM+1], next[MAXM+1], n, k;
int d[MAXN+1];

inline void Add_Edge(int from, int to, int price){
    k++;
    val[k]=to;
    cost[k]=price;
    next[k]=list[from];
    list[from]=k;
}

inline int Left_Son(int p){
    return 2*p;
}
inline int Right_Son(int p){
    return 2*p+1;
}
inline int Father(int p){
    return p/2;
}

inline void Swap_Heap(int p1, int p2){
    int aux=heap[p1];
    heap[p1]=heap[p2];
    heap[p2]=aux;
}
inline void Up_Heap(int p){
    while(p!=1 && d[heap[p]]<d[heap[Father(p)]]){
        Swap_Heap(p, Father(p));
        p=Father(p);
    }
}
inline void Down_Heap(int p){
    int flag=1, q;
    while(flag==1){
        q=-1;
        if(Right_Son(p)<n)
            q=Right_Son(p);
        if(Left_Son(p)<n && (q==-1 || d[heap[q]]>d[heap[Left_Son(p)]]))
            q=Left_Son(p);
        if(q!=-1 && d[heap[q]]<d[heap[p]]){
            Swap_Heap(q, p);
            p=q;
        }
        else
            flag=0;
    }
}

int main(){
    int m;
    FILE*fo;
    fi=fopen("dijkstra.in","r");
    fo=fopen("dijkstra.out","w");
    n=nextnum();m=nextnum();
    k=0;
    for(int i=0;i<m;i++){
        int a=nextnum(), b=nextnum(), c=nextnum();
        Add_Edge(a, b, c);
    }
    int cn=n;
    n=2;
    heap[1]=1;
    d[1]=0;
    poz[1]=1;
    while(n>1){
        int p=list[heap[1]];
        while(p!=0){
            if(luat[val[p]]==0){
                luat[val[p]]=1;
                d[val[p]]=d[heap[1]]+cost[p];
                heap[n]=val[p];
                poz[val[p]]=n++;
                Up_Heap(n-1);
            }
            else if(d[val[p]]>d[heap[1]]+cost[p]){
                d[val[p]]=d[heap[1]]+cost[p];
                Up_Heap(poz[val[p]]);
            }
            p=next[p];
        }
        n--;
        heap[1]=heap[n];
        poz[heap[1]]=1;
        Down_Heap(1);
    }
    for(int i=2;i<=cn;i++)
        fprintf(fo,"%d ", d[i]);
    fclose(fi);
    fclose(fo);
    return 0;
}