#include<fstream>
#include<vector>
#include<queue>
#define DIM 50005
#define str pair< int, int >
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int a, b, c, d[DIM], n, m;
vector< str > v[DIM];
priority_queue< str, vector<str>, greater<str> > q;
int main(){
    fin >> n >> m;
    for( int i = 1; i <= m; i++ ){
        fin >> a >> b >> c;
        v[a].push_back( make_pair( c, b ) );
    }
    for( int i = 1; i <= n; i++ ){
        d[i] = 2000000000;
    }
    d[1] = 0;
    q.push( make_pair( 0, 1 ) );
    while( !q.empty() ){
        int nod = q.top().second;

        if( q.top().first != d[nod] ){
            q.pop();
            continue;
        }

        for( int i = 0; i < v[nod].size(); i++ ){
            int vecin = v[nod][i].second;
            int cost = v[nod][i].first;
            if( d[vecin] > d[nod] + cost ){
                d[vecin] = d[nod] + cost;
                q.push( make_pair( d[vecin], vecin ) );
            }
        }

        q.pop();
    }
    for( int i = 2; i <= n; i++ ){
        fout << ( (d[i] == 2000000000) ? 0 : d[i] ) << " ";
    }
    return 0;
}