#include <fstream>
#include <iostream>
#include <limits.h>
#include <vector>
#include <queue>
using namespace std;
struct arc{
    int y, c;
};
struct elem{
    int x, c;
};
struct comp{
    bool operator()( elem a, elem b ) const
                        //             |
                        //se pune CONST la comparatori STL!!!
                        //vai vai vai...
                        //
                        //imagineaza-ti cat de unsafe e poti
                        //modifica obiectul!!!!
                        //
                        //STL si standardele sale au fost
                        //create in ani de munca si tu nu ai pus
                        //const...
    {

        return a.c > b.c;
    }
};
priority_queue <elem, vector <elem>, comp> q;
vector <arc> v[50005];
int f[50005];
int main(){
    int n, m, i, x, y, c;
    ifstream fin( "dijkstra.in" );
    ofstream fout( "dijkstra.out" );
    fin >> n >> m;
    for( i = 0; i < m; i++ ){
        fin >> x >> y >> c;
        v[x].push_back( { y, c } );
    }
    for( i = 2; i <= n; i++ ){
        f[i] = INT_MAX / 2;
    }
    q.push( { 1, 0 } );
    while( q.empty() == false ){
        x = q.top().x;
        c = q.top().c;
        q.pop();
        ///cout << x << ' ' << f[x] << ' ' << c << '\n';
        if( c != f[x] ){
            continue;
        }
        ///cout << x << ' ' << f[x] << '\n';
        for( i = 0; i < v[x].size(); i++ ){
            y = v[x][i].y;
            if( c + v[x][i].c < f[y] ){
                f[y] = c + v[x][i].c;
                q.push( { y, f[y] } );
            }
        }
    }
    for( i = 2; i <= n; i++ ){
        if( f[i] == INT_MAX / 2 ){
            f[i] = 0;
        }
        fout << f[i] << ' ';
    }
    return 0;
}