#include <bits/stdc++.h>
#define dim 50009
#define inf 1e9 + 1
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m, x, y, cost;
vector< vector< pair< int, int > > > v(dim);
int front = 0, back = 0;
vector<int> coada(dim);
vector<int> d(dim, inf);

int main() {

    fin >> n >> m;

    for(int i = 0; i < m; i++) {
        fin >> x >> y >> cost;
        v[x].push_back( make_pair(y, cost));
    }
    coada[back++] = 1;
    d[1] = 0;


    for(int i = 0; i < n; i++) {
        int capat = back;

        for(; front < capat; front++) {
            int nod = coada[front];

            for(int j = 0; j < v[nod].size(); j++) {

                if( d[ v[ nod ][j].first ] > d[ nod ] + v[ nod ][j].second  ) {
                    coada[back++] = v[nod][j].first;
                    d[ v[ nod ][j].first ] = d[ nod ] + v[ nod ][j].second;
                }
            }
        }
    }


    int capat = back;

        for(; front < capat; front++) {
            int nod = coada[front];

            for(int j = 0; j < v[nod].size(); j++) {

                if( d[ v[ nod ][j].first ] > d[ nod ] + v[ nod ][j].second  ) {
                    fout << "Ciclu negativ!";
                    return 0;
                }
            }
        }


    if(n > 1)
        for(int i = 2; i <= n; i++) 
            fout << d[i] << " ";
        

    return 0;
}