#include <iostream>
#include <fstream>
#include <vector>
#include <tuple>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,x,y,c,dist[50005];
const int inf = 100000000;
vector<tuple<int,int,int>> v;
int main() {
        fin>>n>>m;
        for (int i = 1;i<=m;++i) {
                fin>>x>>y>>c;
                v.emplace_back(x,y,c);
        }
        dist[1] = 0;
        for (int i = 2;i<=n;++i)
                dist[i] = inf;
        for (int i = 1;i<=n-1;++i) {
                for (auto e : v) {
                        int a,b,c;
                        tie (a,b,c) = e;
                        dist[b] = min(dist[a]+c,dist[b]);
                }
        }
        bool negative = 0;
        for (auto e : v) {
                int a,b,c;
                tie (a,b,c) = e;
                if (dist[a]+c<dist[b]) {
                        negative = 1;
                        break;
                }
        }
        if (negative) {
                fout<<"Ciclu negativ!";
        } else {
                for (int i = 2;i<=n;++i)
                        fout<<dist[i]<<" ";
        }
        return 0;
}