#include <stdio.h>
using namespace std;
#define MAX_N    50000
#define MAX_M   250000
#define INF  999999999
struct nod{
    int nr;
    int cost;
    nod *next;
}*First[MAX_N+1],*List;
int N,M;
int *D,*Visited;
void write();
void Insert(int x,int y,int cost){
    nod*q=new nod;
    q->nr=y;
    q->cost=cost;
    if(First[x]==0)
        q->next=0;
    else
        q->next=First[x];
    First[x]=q;
}
void Read(){
    freopen("dijkstra.in","r",stdin);
    scanf("%d %d\n",&N,&M);
    int i,x,y,cost,n=N,m=M;
    D=new int [n+5];
    Visited=new int [n+5];
    for(i=1;i<=m;i++){
        scanf("%d %d %d\n",&x,&y,&cost);
        Insert(x,y,cost);
    }
    fclose(stdin);

}
void Update(int x){
    nod *q=First[x];
    int y,cost;
    while(q){
        y=q->nr;
        cost=q->cost;
        if(Visited[y]==0&&D[y]>D[x]+cost){
            D[y]=D[x]+cost;
        }
        q=q->next;
    }
}
void Dijkstra(int nods){
    int i,n=N,min=0,urm;
    for(i=0;i<=N+1;i++){
        Visited[i]=0;
        D[i]=INF;
    }
    int ac=nods;
    D[ac]=0;
    while(min<INF){
        Visited[ac]=1;
        Update(ac);
        min=INF;
        for(i=1;i<=n;i++){
            if(Visited[i]==0&&min>D[i]){
                min=D[i];
                urm=i;
            }
        }
//        printf("%d/%d -> ",ac,urm);
//        write();
        ac=urm;

    }
}
void write(){
    for(int i=2;i<=N;i++)
        if(D[i]==INF)
            printf("0 ");
        else
            printf("%d ",D[i]);
    printf("\n");
}
int main()
{
    Read();
    Dijkstra(1);
    freopen("dijkstra.in","w",stdout);
    write();
    fclose(stdout);
    return 0;
}