#include <stdio.h>
#define nd 50001
#define inf 1999999999
struct nod{ int val; int cost; nod *urm; }*p[nd];
nod *aux;
int d[nd],x1,x2,c1,i,n,m;
int main()
{
bool ok;
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf("%d %d\n",&n,&m);
for(i=2;i<=n;i++)
    d[i]=inf;
d[1]=0;
for(i=1;i<=m;i++)
    {
        scanf("%d %d %d\n",&x1,&x2,&c1);
        aux=new nod; aux->val=x2; aux->cost=c1; aux->urm=p[x1]; p[x1]=aux;
        if(x1==1)d[x2]=c1;
    }
do
{
ok=true;
for(i=1;i<=n;i++)
    {
        aux=p[i];
        while(aux!=NULL)
            {
                x1=aux->val;
                c1=aux->cost;
                if(d[x1]>d[i]+c1)
                    {
                        d[x1]=d[i]+c1;
                        ok=false;
                    }
                aux=aux->urm;
            }
    }
}
while(ok==false);
for(i=2;i<=n;i++)
    if(d[i]!=inf)printf("%d ",d[i]);
        else printf("0 ");
fclose(stdin);
fclose(stdout);
return 0;
}