#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];
int passed[NMAX];

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

bool bellmanford(int startingNode){
    setup();
    dist[startingNode] = 0;
    bitset <NMAX> inQueue;
    queue <int> q;

    q.push(startingNode);

    int head;

    while(!q.empty()){
        head = q.front();
        q.pop();
        inQueue[head] = 0;

        if(passed[head] > n)
            return false;

        passed[head]++;

        for(auto &it: g[head])
            if(dist[it.first] > dist[head] + it.second){
                dist[it.first] = dist[head] + it.second;
                if(inQueue[it.first] == 0){
                    inQueue[it.first] = 1;
                    q.push(it.first);
                }
            }
    }

    return true;
}


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;
}