#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>

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

const int INF = 1e9;

int main()
{
    int n, m, x, y, d;
    fin >> n >> m;
    vector <vector <pair <int, int>>> ad(n + 1);
    for(int i = 0; i < m; i++){
        fin >> x >> y >> d;
        ad[x].push_back({y, d});
    }
    vector <int> dist(n + 1, INF), nrinq(n + 1);
    vector <bool> inq(n + 1);
    queue <int> q;
    q.push(1);
    inq[1] = true;
    bool ciclu = false;
    dist[1] = 0;
    while(q.size() > 0 && !ciclu){
        int nod = q.front();
        q.pop();
        inq[nod] = false;
        for(auto fiu : ad[nod])
            if(dist[fiu.first] > dist[nod] + fiu.second){
                dist[fiu.first] = dist[nod] + fiu.second;
                if(!inq[fiu.first]){
                    q.push(fiu.first);
                    inq[fiu.first] = true;
                    nrinq[fiu.first]++;
                    if(nrinq[fiu.first] > n)
                        ciclu = true;
                }
            }
    }
    if(ciclu)
        fout << "Ciclu negativ!";
    else
        for(int i = 2; i <= n; i++)
            fout << dist[i] << ' ';
    fin.close();
    fout.close();
    return 0;
}