#include <stdio.h>
using namespace std;
#define MAX_N 50000
#define MAX_M 250000
#define MAX_V 1000
#define INF 999999999
struct nod{
    int nr;
    int cost;
    nod *next;
}*First[MAX_N+1];
int N,M;
bool Visited[MAX_N+5];
nod *V[MAX_V+5],*U[MAX_V+5];
int D[MAX_N+5];
void InsertInV(int min,int x,int y){
    nod *q=new nod;
    q->nr=x;
    q->cost=y;
    q->next=0;
    if(V[min]==0){
        V[min]=U[min]=q;
    }
    else{
        U[min]->next=q;
        U[min]=q;
    }
}
void DeleteFromV(int min){
    nod *q=V[min];
    if(U[min]==V[min])
        U[min]=V[min]=0;
    else
        V[min]=q->next;
    delete q;
}
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,c;
    for(i=1;i<=M;i++){
        scanf("%d %d %d\n",&x,&y,&c);
        Insert(x,y,c);
    }
    for(i=0;i<=N+1;i++)
        D[i]=INF;
    D[1]=0;
    fclose(stdin);
}
int ReturnMin(){
    int i,y,x;
    for(i=0;i<=MAX_V;i++){
        go:
        if(V[i]!=0){
            y=V[i]->cost;
            x=V[i]->nr;
            while(D[y]<=D[x]+i){
                DeleteFromV(i);
                if(V[i]==0){
                    i++;
                    goto go;
                }
            }
            return i;

        }
    }
    return -1;
}
void PutInV(int x){
    nod *q=First[x];
    int y,c;
    while(q){

        y=q->nr;
        c=q->cost;
        if(D[y]>D[x]+c){
            InsertInV(c,x,y);
        }
        q=q->next;
    }
}
void write(int limit){
    nod *q;
    for(int i=0;i<=limit;i++){
        printf("%d ->",i);
        if(V[i]!=0){
            q=V[i];
            while(q){
                printf(" (%d, %d) ",q->nr,q->cost);
                q=q->next;
            }
        }
        printf("\n");
    }
}
void Resolve(){
    int i,ant=1,min;
    Visited[1]=1;
    for(i=2;i<=N;i++){
        PutInV(ant);
        min=ReturnMin();
//        printf("%d %d",ant,min);
        if(min<0){
            break;
        }
        ant=V[min]->cost;
        D[ant]=D[V[min]->nr]+min;
        Visited[ant]=1;
        //printf(" -> %d %d\n",ant,D[ant]);
        DeleteFromV(min);
    }
}
void Write(){
    for(int i=2;i<=N;i++){
        if(D[i]==INF)
            D[i]=0;
        printf("%d ",D[i]);
    }
    printf("\n");
}
int main()
{
    Read();
    Resolve();
//    printf("\n\n");
    freopen("dijkstra.out","w",stdout);
    Write();
/*    PutInV(1);
    printf("%d\n",ReturnMin());
    DeleteFromV(2);
    Visited[5]=1;
    PutInV(5);
    printf("%d\n",ReturnMin());
    DeleteFromV(2);
    Visited[8]=1;
    PutInV(8);
    printf("%d\n",ReturnMin());
    DeleteFromV(3);
    Visited[3]=1;
    PutInV(7);
    printf("%d\n",ReturnMin());*/
//    write(10);
    return 0;
}