#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 InsertFunction(nod *p,int nr,int cost){
    nod *q=new nod;
    q->nr=nr;
    q->cost=cost;
    q->next=p->next;
    p->next=q;
}
void InsertInList(nod *p,int nr,int cost){
    if(p->next==0){
        InsertFunction(p,nr,cost);
        return;
    }
    if(p->next->nr==nr){
        if(cost<p->next->cost)
            InsertFunction(p,nr,cost);
        return;
    }
    if(cost<=p->next->cost){
        InsertFunction(p,nr,cost);
        return;
    }
    InsertInList(p->next,nr,cost);
}
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;
            InsertInList(List,y,D[y]);
        }
        q=q->next;
    }
}
void write(nod *p){
    if(p){
        printf("%d %d\n",p->nr,p->cost);
        write(p->next);
    }
}
void Delete(){
    nod *q=List->next;
    List->next=q->next;
    delete q;
}
int ReturnMin(){
    nod *q=List->next;
    if(q==0)
        return 0;
    int nr=q->nr;
    if(Visited[nr]==1){
        Delete();
        return ReturnMin();
    }
    Delete();
    return nr;
}
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;
    List=new nod;
    List->next=0;
    while(ac>0){
        Visited[ac]=1;
        Update(ac);
        urm=ReturnMin();
/*        printf("%d/%d -> ",ac,urm);
        Write();
        write(List->next);*/
        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.out","w",stdout);
    Write();
    fclose(stdout);
    return 0;
}