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

using namespace std;

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


vector<pair <int, pair<int, int> > >vec;
int n, m, d[50005], tata[50005];

int main(){
    fin>>n>>m;
    for(int i=1; i<=m; i++){
        int x, y, z;
        fin>>x>>y>>z;

        vec.push_back(make_pair(z , make_pair(x, y)));

    }

    for(int i=1; i<=n; i++) d[i]= 1e9;
    d[1] = 0;

    for(int k=1; k<n; k++){
        for(auto i : vec){
            int c = i.first, x= i.second.first, y=i.second.second;
            if(d[y] > d[x] + c){
                d[y] = d[x] + c;
                tata[y] = x;    
            }
        }
    }

    for(auto i : vec){
            int c = i.first, x= i.second.first, y=i.second.second;
            if(d[y] > d[x] + c){
                d[y] = d[x] + c;
                tata[y] = x;
                fout<<"Ciclu negativ!";
                return 0;
            }
        }
    for(int i=2; i<=n; i++)
        fout<<d[i]<<' ';
    return 0;
}