#include <iostream>
#include<fstream>
#include<stdio.h>
#include<string.h>

using namespace std;

const int LGMAX = int(5e4) + 1;
int viz[LGMAX], dst[LGMAX],
    n,m;
typedef struct nod
    {
        int inf,d;
        nod *urm;
    } TNOD;
TNOD *v[LGMAX];

void add( int a, int b, int ds)
{
    TNOD *p = new TNOD;
    p->inf = a;
    p->d = ds;
    p->urm = v[b];
    v[b] = p;
}

void citire()
{
    int i,D,x,y;
    ifstream in("dijkstra.in");
    in>>n>>m;
    for( i=1;i<=m; i++ )
    {
        in>>x>>y>>D;
        add( y, x, D );
    }
}

void dicky()
{
    int min,nodu,i;
    memset(dst,int(3e4),sizeof(dst));
    dst[1] = 0;
   for( int j=1; j<=n; j++ )
    {
        min = (1<<18);
        for( i=1; i<=n; i++ )
            if( dst[i]<min && !viz[i] )
                min = dst[i],
                nodu = i;
        viz[nodu] = 1;

        TNOD *p=v[nodu];
        while(p)
        {
            if( dst[p->inf]>dst[nodu] + p->d )
                dst[p->inf] = dst[nodu] + p->d;
            p=p->urm;
        }
    }

}

void afish()
{
    int i;
    for( i=2; i<=n; i++ )
        if(dst[i]==-1) printf("0 ");
        else printf("%d ",dst[i] );
    printf("\n");
}


int main()
{
    freopen("dijkstra.out","w",stdout);
    citire();
    dicky();
    afish();
    return 0;
}