#include<fstream>
#include<vector>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int sz,n,m,poz[50001];
pair<int,int>heap[50001];
vector< pair<int,int> >h[50001];
void up( int p ){
    while( p > 1 && heap[p].first < heap[p/2].first ){
        swap( poz[ heap[p/2].second ], poz[ heap[p].second ]  );
        swap( heap[p/2], heap[p] );
        p/=2;
    }
    return;
}
void down( int p ){
    while( p*2 <= sz  ){
        int t=p*2;
        if( t < sz && heap[t+1].first < heap[t].first ){
            t ++;
        }
        if( heap[p].first > heap[t].first ){
            swap( poz[ heap[t].second ], poz[ heap[p].second ] );
            swap( heap[t], heap[p] );
            p = t;
        }
        else{
            break;
        }
    }
    return;
}
void elimina( ){
    swap( heap[sz], heap[1] );
    swap( poz[ heap[sz].second ] , poz[ heap[1].second ] );
    sz--;
    down( 1 );
}
int d[50001],x,y,i,a,b,c,j;
int main(){
    in >> n >> m;
    sz = n;
    heap[1].first = 0;
    heap[1].second = 1;
    poz[1] = 1;
    for( int i = 2; i <= n; i ++ ){
        heap[i].first = 1e9;
        heap[i].second = i;
        poz[ i ] = i;
    }
    for( i = 1; i <= m; i ++ ){
        in >> a >> b >> c;
        h[a].push_back( make_pair(b,c) );
    }
    for( i = 1; i <= n; i ++ ){
        x = heap[1].second;
        y = heap[1].first;
        d[x] = heap[1].first;
        elimina();
        for( j = 0; j < h[x].size(); j ++ ){
            heap[ poz[ h[x][j].first ] ].first = min( heap[ poz[ h[x][j].first ] ].first, y + h[x][j].second );
            up( poz[ h[x][j].first ] ); down( poz[ h[x][j].first ] );
        }
    }
    for( i = 2; i <= n; i ++ ){
        out<<d[i]<<" ";
    }
    return 0;
}