#include <cstdio>

using namespace std;

struct muchie{
                int x,y,c;
             }G[250005];

const int inf = (2e9);

int n,m,i,d[50005],ok;

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d", &n, &m);
    for (i=1;i<=m;i++)
    {
        scanf("%d %d %d", &G[i].x, &G[i].y, &G[i].c);
        if (G[i].x==1) d[G[i].y]=G[i].c;
    }
    for (i=2;i<=n;i++)
        if (!d[i]) d[i]=inf;
    do{
        ok=1;
        for (i=1;i<=m;i++)
            if (d[G[i].y]>d[G[i].x]+G[i].c) d[G[i].y]=d[G[i].x]+G[i].c, ok=0;
    }while (!ok);
    for (i=2;i<=n;i++)
        if (d[i]!=inf) printf("%d ", d[i]);
        else printf("0 ");
    return 0;
}