#include <cstdio>
#define INF 2000000000
using namespace std;

FILE *f;
FILE *g;

struct muchie
{
    int a,b,c;
} M[250010];

int n,m,d[50010];

void citire()
{
    f=fopen("dijkstra.in","r");
    fscanf(f,"%d %d",&n,&m);
    for(int i=1;i<=m;i++)
        fscanf(f,"%d %d %d",&M[i].a,&M[i].b,&M[i].c);
    fclose(f);
}

void init()
{
    for(int i=1;i<=n;i++)
        d[i]=INF;
    d[1]=0;
}

void bell()
{
    init();
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
            if(d[M[j].a]+M[j].c<d[M[j].b])
                d[M[j].b]=d[M[j].a]+M[j].c;
}
int main()
{
    citire();
    bell();
    g=fopen("dijkstra.out","w");
    for(int i=2;i<=n;i++)
        fprintf(g,"%d ",d[i]<INF?d[i]:0);
    fprintf(g,"\n");
    fclose(g);
    return 0;
}