#include<stdio.h>
#define Nmax 50001
#define inf 0x3f3f

int n,m,s,i,d[Nmax];
char u[Nmax];

struct nod
{
    int drum,cost;
    nod *urm;
} *l[Nmax];

void add(nod *&inc,int info,int c)
{
    nod *q=new nod;
    q->drum=info;
    q->cost=c;
    q->urm=inc;
    inc=q;
}

void dijkstra()
{
    for ( int i = 2; i <= n; ++i )
        d[i] = inf;

    int min, pmin = 0;
    for ( int i = 1; i <= n; ++i )
    {
        min = inf;

        for ( int j = 1; j <= n; ++j )
            if ( d[j] < min && !u[j] )
                {
                min = d[j];
                pmin = j;
                }

        u[pmin] = 1;

        nod *t = l[pmin];

        while (t)
        {
            if ( d[ t->drum ] > d[pmin] + t->cost )
                d[ t->drum ] = d[pmin] + t->cost;

            t = t->urm;
        }
    }
}

int main()
{
    int x,y,z;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
        {
        scanf("%d%d%d",&x,&y,&z);
        add(l[x],y,z);
        }
    dijkstra();
    for(int i=2;i<=n;++i)
        printf("%d ", d[i] == inf ? 0 : d[i]);
    printf("\n");
    return 0;
}