#include <bits/stdc++.h>

using namespace std;

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

struct edge{
    int start, dest, weight;
};

const int NMAX = 5e4 + 4, DMAX = 250 * 1e6 + 5;
int n, m;
vector < edge > g;
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;

    for(i = 1; i < n; ++i){
        for(auto &it: g){
            if(dist[it.dest] > dist[it.start] + it.weight)
                dist[it.dest] = dist[it.start] + it.weight;
        }
    }

    bool ok = false;
    for(auto &it: g){
            if(dist[it.dest] > dist[it.start] + it.weight)
                dist[it.dest] = dist[it.start] + it.weight, 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.push_back({a, b, c});
    }

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


    return 0;
}