#include <stdio.h>
#define DIM 505
#define MOD (40*DIM)
#define INF 2147483647
struct nod {int x,c;
            nod *urm;} *lst[DIM];
int cost[DIM],q[MOD],viz[DIM];
int n,m;
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 read ()
{
    char a[DIM];
    int i,j,x,y,ct;
    scanf ("%d%d\n",&n,&m);
    for (i=1; i<=m; ++i)
    {
        gets (a);
        for (j=x=0; a[j]>='0' && a[j]<='9'; ++j)
            x=x*10+a[j]-'0';
		for (y=0, ++j; a[j]>='0' && a[j]<='9'; ++j)
			y=y*10+a[j]-'0';
		for (ct=0, ++j; a[j]>='0' && a[j]<='9'; ++j)
			ct=ct*10+a[j]-'0';
		add (x,y,ct);
    }
    for (i=2; i<=n; ++i)
        cost[i]=INF;
}
void solve ()
{
    nod *p;
    int i,in,sf;
    for (q[in=sf=1]=1; in<=sf; ++in)
    {
        viz[q[in%MOD]]=0;
        for (p=lst[q[in%MOD]]; p; p=p->urm)
            if (cost[q[in%MOD]]+p->c<cost[p->x])
            {
                cost[p->x]=cost[q[in%MOD]]+p->c;
                if (!viz[p->x])
                {
                    ++sf;
                    q[sf%MOD]=p->x;
                    viz[p->x]=1;
                }
            }
    }
    for (i=2; i<=n; ++i)
        if (cost[i]!=INF)
            printf ("%d ",cost[i]);
        else
            printf ("0 ");
}
int main ()
{
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);
    read ();
    solve ();
    return 0;
}