#include<stdio.h>
#define Nmx 50001
#define MOD (41*Nmx)
#define INF 2147483000

int n,m;
int viz[Nmx],q[MOD];
int Costuri[Nmx];

struct nod
{
    nod *urm;
    int inf;
    int cost;
};

nod *G[Nmx];

void add(int x,int y,int c)
{
    nod *aux;
    aux=new nod;
    aux->urm=G[x];
    aux->inf=y;
    aux->cost=c;
    G[x]=aux;
}


void citire()
{
    scanf("%d%d",&n,&m);
    int x,y,c;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        add(x,y,c);
        Costuri[i]=INF;
    }
    Costuri[1]=0;
}

void solve()
{
    int st=1,dr=1;
    q[1]=1;
    while(st<=dr)
    {
      viz[q[st%MOD]]=0;
      for (nod *p=G[q[st%MOD]]; p; p=p->urm)
          if (Costuri[q[st%MOD]]+p->cost<Costuri[p->inf])
           {
             Costuri[p->inf]=Costuri[q[st%MOD]]+p->cost;
             if (!viz[p->inf])
               {
                   ++dr;
                   q[dr%MOD]=p->inf;
                   viz[p->inf]=1;
               }
           }
        ++st;
    }
    for(int i=2;i<=n;i++)
        if(Costuri[i]!=INF) printf("%d ",Costuri[i]);
            else printf("0 ");
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    citire();

    solve();

    return 0;
}