#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int MAX_N = 5e4;
vector<pair<int, int>> bords[1 + MAX_N];
int dist[1 + MAX_N];
int viz[1 + MAX_N];
bool is_in_q[1 + MAX_N];

const int inf = 1e9;

bool BellmanFord( int n ) {
    queue<int> bellman;
    bellman.push( 1 );

    while ( bellman.size() ) {
        int t = bellman.front();
        bellman.pop();
        if ( ++ viz[t] == n )
            return 0;
        is_in_q[t] = 0;

        for ( pair<int, int> a : bords[t] )
            if ( dist[t] + a.second < dist[a.first] ) {
                dist[a.first] = dist[t] + a.second;
                if ( !is_in_q[a.first] ) {
                    bellman.push( a.first );
                    is_in_q[a.first] = 1;
                }
            }
    }

    return 1;
}

int main() {
    ifstream fin( "bellmanford.in" );
    ofstream fout( "bellmanford.out" );

    int n, m;
    fin >> n >> m;

    for ( int i = 0; i < m; i ++ ) {
        int u, v, c;
        fin >> u >> v >> c;
        bords[u].emplace_back( v, c );
    }

    for ( int i = 2; i <= n; i ++ )
        dist[i] = inf;

    if ( !BellmanFord( n ) )
        fout << "Ciclu negativ!";
    else
        for ( int i = 2; i <= n; i ++ )
            fout << dist[i] << ' ';

    return 0;
}