#include <cstdio>
#define vv 50005
#define inf 0x3f3f3f3f

using namespace std;

struct nod
    {
        int val,cost;
        nod *next;
    };

nod *w[vv];
int n,m,q[vv],d[vv];

void citire()
{
    freopen("dijkstra.in","r",stdin);
    scanf("%d%d", &n, &m);
    int z,x,c;
    for (int i=1; i<=n; i++)
        w[i]=NULL;
    nod *p;
    for (int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &z, &x, &c);
        p=new nod;
        p->val=x;
        p->cost=c;
        p->next=w[z];
        w[z]=p;
    }
    fclose(stdin);
}

int min()
{
    int w=0,min=inf;
    for (int i=1; i<=n; i++)
        if (!q[i] && d[i]<min)
        {
            min=d[i];
            w=i;
        }
    q[w]=1;
    return w;
}

void dijkstra()
{
    for (int i=2; i<=n; i++)
        d[i]=inf;
    int k;
    for (int i=1; i<=n; i++)
    {
        k=min();
        if (d[k]==inf)
            return;
        for (nod *p=w[k]; p; p=p->next)
            if (d[k]+p->cost<d[p->val])
                d[p->val]=d[k]+p->cost;
    }
}

void afisare()
{
    freopen("dijkstra.out","w",stdout);
    for (int i=2; i<=n; i++)
        if (d[i]!=inf)
            printf("%d ", d[i]);
        else
            printf("0 ");
    fclose(stdout);
}

int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}