#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e4 + 4, DMAX = 1e9;
int n, m;
vector < pair <int, int> > g[NMAX];
long long dist[NMAX];

void setup(){
    for(int i = 0; i < NMAX; ++i) dist[i] = DMAX;
}

bool bellmanford(int startingNode){
    setup();
    dist[startingNode] = 0;

    int i, j;

    for(i = 1; i < n; ++i){
        for(j = 1; j <= n; ++j)
            for(auto &it: g[j])
                if(dist[it.first] > dist[j] + it.second)
                    dist[it.first] = dist[j] + it.second;
    }

    bool ok = false;

    for(i = 1; i < n; ++i){
        for(j = 1; j <= n; ++j)
            for(auto &it: g[j])
                if(dist[it.first] > dist[j] + it.second)
                    dist[it.first] = dist[j] + it.second, ok = true;
    }

    return !ok;
}


int main()
{
    fin >> n >> m;

    for(int i = 1; i <= n; ++i){
        int a, b, c;
        fin >> a >> b >> c;
        g[a].push_back({b, c});
    }

    if(bellmanford(1))
        for(int i = 2; i <= n; ++i)
            fout << dist[i] << ' ';
    else fout << "Ciclu negativ!";


    return 0;
}