//#include <algorithm>
//#include <vector>
//using namespace std;
//
//#define DIM 50001
//#define INF 0x3f3f3f3f
//
//int N, M;
//int cnt, cst[ DIM ], poz[ DIM ], heap[ DIM ];
//vector < pair <int, int> > v[ DIM ];
//
//inline void heap_up( int nod ) {
//
//    int aux;
//
//    while( nod > 1 ) {
//
//        aux = nod>>1;
//        if( cst[ heap[ aux ] ] > cst[ heap[ nod ] ] ) {
//
//            swap( heap[ aux ], heap[ nod ] );
//            poz[ heap[ aux ] ] = aux;
//            poz[ heap[ nod ] ] = nod;
//            nod = aux;
//        }
//        else
//            return;
//    }
//}
//
//inline void heap_down( int nod ) {
//
//    int aux;
//
//    while( nod <= cnt ) {
//
//        aux = nod;
//        if( nod<<1 <= cnt ) {
//
//            aux = nod<<1;
//            if( aux+1 <= cnt && cst[ heap[ aux+1 ] ] < cst[ heap[ aux ] ] )
//                ++aux;
//        }
//        else
//            return;
//
//        if( cst[ heap[ aux ] ] < cst[ heap[ nod ] ] ) {
//
//            swap( heap[ aux ], heap[ nod ] );
//            poz[ heap[ aux ] ] = aux;
//            poz[ heap[ nod ] ] = nod;
//            nod = aux;
//        }
//        else
//            return;
//    }
//}
//
//inline void heap_push( const int &ind ) {
//
//    heap[ ++cnt ] = ind;
//    poz[ ind ] = cnt;
//    heap_up( cnt );
//}
//
//inline void heap_pop() {
//
//    heap[ 1 ] = heap[ cnt-- ];
//    poz[ heap[ 1 ] ] = 1;
//    heap_down( 1 );
//}
//
//int main() {
//
//    freopen( "dijkstra.in", "r", stdin );
//    freopen( "dijkstra.out", "w", stdout );
//
//    int i, x, y, c, ind;
//    vector < pair <int, int> > :: iterator it;
//
//    scanf( "%d %d", &N, &M );
//    for( i = 0; i < M; ++i ) {
//
//        scanf( "%d %d %d", &x, &y, &c );
//        v[ x ].push_back( make_pair( y, c ) );
//    }
//
//    memset( cst, INF, sizeof( cst ) );
//    ++cnt;
//    heap_push( 1 );
//    cst[ 1 ] = 0;
//    poz[ 1 ] = 1;
//    while( cnt ) {
//
//        ind = heap[ 1 ];
//        heap_pop();
//        for( it = v[ ind ].begin(); it != v[ ind ].end(); ++it )
//            if( cst[ ind ] + it->second < cst[ it->first ] ) {
//
//                cst[ it->first ] = cst[ ind ] + it->second;
//                if( poz[ it->first ] )
//                    heap_up( poz[ it->first ] );
//                else
//                    heap_push( it->first );
//            }
//    }
//
//    for( i = 2; i <= N; ++i )
//        if( cst[ i ] == INF )
//            printf( "0 " );
//        else
//            printf( "%d ", cst[ i ] );
//
//    return 0;
//}

#include<algorithm>
using namespace std;

#define DIM 50001
#define INF 1<<30

struct djk{
    int poz,val;};

struct graf{
    int nod,cost;
    graf *urm;};

int n,m,cnt,h[DIM];
djk a[DIM];
graf *lst[DIM];

void add(int nod0,int nod1,int cost){
    graf *p=new graf;

    p->nod=nod1;
    p->cost=cost;
    p->urm=lst[nod0];
    lst[nod0]=p;}

void init(){
    int i;

    for(i=2; i<=n; ++i){
        a[i].val=INF;
        a[i].poz=-1;}}

void swap(int x,int y){
    int aux;

    aux=h[x];
    h[x]=h[y];
    h[y]=aux;}

void uph(int k){
    int aux;

    while(k>1){
        aux=k>>1;
        if(a[h[aux]].val>a[h[k]].val){
            a[h[k]].poz=aux;
            a[h[aux]].poz=k;
            swap(aux,k);
            k=aux;}
        else
            return;}}

void downh(int k){
    int aux;

    while(k<=cnt){
        aux=k;
        if((k<<1)<=cnt){
            aux=k<<1;
            if(aux+1<=cnt)
                if(a[h[aux+1]].val<a[h[aux]].val)
                    ++aux;}
        else
            return;
        if(a[h[k]].val>a[h[aux]].val){
            a[h[k]].poz=aux;
            a[h[aux]].poz=k;
            swap(k,aux);
            k=aux;}
        else
            return;}}

void insert(int k){

    h[++cnt]=k;
    a[h[cnt]].poz=cnt;
    uph(cnt);}

void cut(){

	h[1]=h[cnt--];
	a[h[1]].poz=1;
	downh(1);}

void dijkstra(){
	int aux;
	graf *p;

    a[1].poz=1;
    h[++cnt]=1;
	while(cnt){
		aux=h[1];
		cut();
        for(p=lst[aux]; p; p=p->urm)
            if(a[aux].val+p->cost<a[p->nod].val){
                a[p->nod].val=a[aux].val+p->cost;
                if(a[p->nod].poz!=-1)
					uph(a[p->nod].poz);
                else
                    insert(p->nod);}}}

void solve(){
    int i,nod0,nod1,cost;

    scanf("%d%d",&n,&m);
    for(i=0; i<m; ++i){
        scanf("%d%d%d",&nod0,&nod1,&cost);
        add(nod0,nod1,cost);}
    init();
    dijkstra();
    for(i=2; i<=n; ++i)
        if(a[i].val==INF)
            printf("0 ");
        else
            printf("%d ",a[i].val);}

int main(){

    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    solve();
    return 0;}