#include<bits/stdc++.h>
using namespace std;

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

const int DIM = 50005;

int N, M, viz[DIM];
bool f[DIM], ciclu;
long long dist[DIM];
vector< pair<int,int> > edge[DIM];
queue<int> q;

void bf( int sursa ){
    ciclu = false;
    for( int i = 1; i <= N; i++ )
        dist[i] = (1LL<<62);
    dist[sursa] = 0;
    f[sursa] = true;
    viz[sursa] = 1;
    q.push( sursa );
    while( !q.empty() && ciclu == false ){
        int nod = q.front();
        for( int i = 0; i < edge[nod].size() && ciclu == false; i++ ){
            int vec = edge[nod][i].first;
            int cost = edge[nod][i].second;
            if( dist[vec] > dist[nod] + cost ){
                dist[vec] = dist[nod] + cost;
                viz[vec]++;
                if( viz[vec] == N )
                    ciclu = true;
                if( f[vec] == false )
                    f[vec] = true, q.push( vec );
            }
        }
        f[nod] = false;
        q.pop();
    }
    return;
}

int main(){

    fin >> N >> M;
    for( int i = 1; i <= M; i++ ){
        int x, y, z; fin >> x >> y >> z;
        edge[x].push_back( {y, z} );
    }

    bf( 1 );
    if( ciclu == true ){
        fout << "Ciclu negativ!\n";
        return 0;
    }

    for( int i = 2; i <= N; i++ )
        fout << dist[i] << " ";
    return 0;
}