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

FILE *f;
FILE *g;

typedef struct nod
{
    int inf,c;
    nod *urm;
} NOD;
typedef NOD *graf[50010];
graf G;

int n,m,d[50010];
bool viz[50010];

void citire()
{
    f=fopen("dijkstra.in","r");
    fscanf(f,"%d %d",&n,&m);
    int a,b,c;
    NOD *p;
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d",&a,&b,&c);
        p=new NOD;
        p->inf=b; p->urm=G[a]; p->c=c;
        G[a]=p;
    }
    fclose(f);
}

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

void bell()
{
    init();
    for(int i=1;i<n;i++)
        for(int j=1;j<=n;j++)
            if(viz[i])
            {
                viz[i]=0;
                NOD *p=G[i];
                while(p)
                {
                    if(d[i]+p->c<d[p->inf])
                    {
                        d[p->inf]=d[i]+p->c;
                        viz[p->inf]=1;
                    }
                    p=p->urm;
                }
            }
}
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;
}