#include <fstream>
#include <queue>

using namespace std;

ifstream cin ( "dijkstra.in" );
ofstream cout ( "dijkstra.out" );

#define N_MAX 50000
#define INF (1 << 30)

priority_queue<pair<int, int>> dijkstra;
vector<pair<int, int>> G[N_MAX + 1];
int ans[N_MAX + 1];

void DIJKSTRA() {
    while ( !dijkstra.empty() ) {
        pair<int, int> elem = dijkstra.top();
        dijkstra.pop();
        for ( auto copil : G[elem.second] ) {
            if ( ans[copil.first] < elem.first + copil.second * -1 ) {
                if ( copil.first == 6 ) {
                    ans[copil.first] = -1;
                }
                ans[copil.first] = elem.first + copil.second * -1;
                dijkstra.push ( {ans[copil.first], copil.first} );
            }
        }
    }
}

int main() {
    int n, m, i, a, b, cost;
    cin >> n >> m;
    for ( i = 0; i < m; i++ ) {
        cin >> a >> b >> cost;
        G[a].emplace_back(b, cost);
    }
    dijkstra.push( {-1 , 1} );
    ans[1] = -1;
    for ( i = 2; i <= n; i++ ) {
        ans[i] = -INF;
    }
    DIJKSTRA();
    for ( i = 2; i <= n; i++ ) {
        if ( ans[i] != -INF )
            cout << ( ans[i] + 1 ) * -1 << " ";
        else
            cout << "0 ";
    }
    return 0;
}