#include <iostream>
#include <fstream>
#include <vector>
#include <tuple>
#include <queue>
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;
        queue<int> q;
        q.push(1);
        while(!q.empty()) {
                int crtn = q.front();
                q.pop();
                for (auto e : v) {
                        int a,b,c;
                        tie (a,b,c) = e;
                        if (dist[a]+c<dist[b]) {
                                dist[b] = min(dist[a]+c,dist[b]);
                                q.push(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;
}