#include <stdio.h>
#define max 100010
#define inf 1000000
struct lista
{
    int nod,cost;
    lista *next;
};
lista *g[max],*p;
int n,i,j,m,k,c,d[max],post[max],nr,u;
char s[max];
void push(int i,int j,int c)
{
    lista *p=new lista;
    p->cost=c;
    p->nod=j;
    p->next=g[i];
    g[i]=p;
}
void dfs(int nod)
{
    lista *p;
    s[nod]=1;
    for(p=g[nod]; p!=NULL; p=p->next)
     if(!s[p->nod]) dfs(p->nod);
    post[++nr]=nod;
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(k=1; k<=m; k++)
    {
        scanf("%d%d%d",&i,&j,&c);
        push(i,j,c);
    }
    for(i=1; i<=n; i++) d[i]=inf;
    d[1]=0;
    dfs(1);
    for(i=nr; i>0; i--)
    {
        u=post[i];
        for(p=g[u]; p!=NULL; p=p->next)
         if(d[p->nod]>d[u]+p->cost)
          d[p->nod]=d[u]+p->cost;
    }
    for(i=2; i<=n; i++)
     if(d[i]!=inf) printf("%d ",d[i]);
     else printf("0 ");
    return 0;
}