#include <bits/stdc++.h>
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#define MOD 1000000007
int dist[50005], copie[100005][3], stare[100005], ciclu[1005], v[100005][3], viz[100005];
int n, m, i, j, x, y, C,l, p, q, r,a, b, mx = -2e9, mn = 2e9, val, k, c, z;
long long nr = 0;
bool gasit = false;
vector<int> adj[100005];
vector<pair<double,double>> intervale;

struct Muchie
{
    int x, y;
    long long cost;
};

int main()
{
    int S, A, B;
    fin >> n >> m;
    vector<Muchie> muchii;
    for(i = 1; i <= n; i++)
    {
        fin >> x >> y >> z;
        muchii.push_back({x, y, z});
    }

    for(i = 1; i <= n; i++)
        dist[i] = 2e9;
    dist[1] = 0;
    for(i = 1; i < n; i++)
        for(j = 0; j < muchii.size(); j++)
        {
            int x = muchii[j].x;
            int y = muchii[j].y;
            long long cost = muchii[j].cost;
            if(dist[x] != 2e9 && dist[x] + cost < dist[y])
                dist[y] = dist[x] + cost;
        }

    bool ciclu_negativ = false;
    for(j = 0; j < muchii.size(); j++)
    {
        int x = muchii[j].x;
        int y = muchii[j].y;
        long long cost = muchii[j].cost;
        if(dist[x] != 2e9 && dist[x] + cost < dist[y])
        {
            ciclu_negativ = true;
            break;
        }
    }
    if(ciclu_negativ) fout << "Ciclu negativ!";
    else
    {
        for(i = 2; i <= n; i++)
            fout << dist[i] << " ";
    }

    return 0;
}