#include<stdio.h>
#define INF 1<<30-1
#define DIM 5005
struct nod
{
    int x,c;
    nod *urm;
} *lst[DIM];
int d[DIM],s[DIM],n;
void add (int a,int b,int c)
{
    nod *p=new nod;
    p->x=b;
    p->c=c;
    p->urm=lst[a];
    lst[a]=p;
}
void refresh ()
{
    int i,j;
    nod *p;
    for(i=2;i<=n;++i)
        d[i]=INF;
    for(p=lst[1];p;p=p->urm)
        d[p->x]=p->c;
}
void read ()
{
    int i,m,x1,x2,x3;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
        scanf("%d%d%d",&x1,&x2,&x3),add(x1,x2,x3);
}
void solve ()
{
    int min2,i,j,min;
    nod *p;
    for(i=1;i<=n;++i)
    {
		min=INF;
		for(j=2;j<=n;++j)
			if(d[j]<min && s[j]==0)
			{
				min=d[j];
				min2=j;
			}
		s[min2]=1;
		for(p=lst[min2];p;p=p->urm)
			if(d[min2]+p->c<d[p->x])
                d[p->x]=p->c+d[min2];
    }
}
void show ()
{
    int i;
    for(i=2;i<=n;++i)
        if(d[i]==INF)
            printf("0 ");
        else
            printf("%d ",d[i]);
}
int main ()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    read ();
    refresh ();
    solve ();
    show ();
    return 0;
}