#include <iostream>
#include <queue>
#include <fstream>
#include <vector>
using namespace std;

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

struct arbore{
    int a,b,c;
};

int main()
{

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

    vector<arbore>mc;

    for(int i=1;i<=m;i++){

        int a,b,c;
        fin>>a>>b>>c;

        mc.push_back({a,b,c});
    }

    vector<int>d(n+1,1e9);

    d[1] = 0;

    for(int i=1;i<n;i++){

        for(auto j : mc)
            if(d[j.a] != 1e9 && d[j.a] + j.c < d[j.b])
                d[j.b] = d[j.a] + j.c;

    }

    for(auto j : mc){

        if(d[j.a] != 1e9 && d[j.a] + j.c < d[j.b]){

            fout<<"Ciclu negativ!";
            return 0;
        }
    }

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

    return 0;
}