#include<stdio.h>
#include<stdlib.h>
#include<fstream>
#define INF 2000000000
#define NMAX 50005
using namespace std;
typedef struct nod{int x,d; nod *urm; }NODE;
NODE *v[50005];
int n,m;
int minim[NMAX];
int c[2][600000];

void citire()
{
    ifstream f("dijkstra.in");
    f>>n>>m;
    int x,y,d;
    NODE *q;
    for(int i=1;i<=m;++i)
    {
        f>>x>>y>>d;
        q=(NODE*)malloc(sizeof(NODE));
        q->x=y;
        q->d=d;
        q->urm=v[x];
        v[x]=q;
    }
}

void dfs()
{
    for(int i=1;i<=n;++i) minim[i]=INF;
    int p,u,curent;
    NODE *q;
    p=u=0;
    c[0][0]=1;
    while(p<=u)
    {
        curent=c[0][p];
        q = v[curent];
        if(c[1][p]>minim[curent]) { p++; continue; }
        while(q)
        {
            if(minim[q->x]>q->d+c[1][p])
            {
                c[0][++u]=q->x;
                c[1][u]=q->d+c[1][p];
                minim[q->x]=c[1][u];
            }
            q=q->urm;

        }
        ++p;
    }
}

void scriere()
{
    FILE *f=fopen("dijkstra.out","w");
    for(int i=2;i<=n;++i)
        if(minim[i]!=INF) fprintf(f,"%d ",minim[i]);
        else fprintf(f,"0 ");
    fclose(f);
}

int main()
{
    citire();
    dfs();
    scriere();
    return 0;
}