#include <bits/stdc++.h>
#define llong long long
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");



vector<vector<pair<llong, llong>>> G;
vector<llong> dist;

llong n, m;

void Bellman_Ford(int source){

    vector<bool> in_queue(n + 1, false);
    vector<llong> ap(n + 1, 0);
    queue<llong> q;
    dist[source] = 0;
    q.push(source);
    in_queue[source] = true;
    ap[source]++;

    bool negative_cycle = false;
    while(q.size() > 0 && !negative_cycle){
        int x = q.front();
        q.pop();
        in_queue[x] = false;

        for(auto a : G[x]){
            if(dist[x] + a.second < dist[a.first]){
                dist[a.first] = dist[x] + a.second;

                if(!in_queue[a.first]){
                    if(ap[a.first] > n){
                        negative_cycle = true;
                        break;
                    } else{
                        q.push(a.first);
                        in_queue[a.first] = true;
                        ap[a.first]++;
                    }

                }

            }
        }
    }

    if(negative_cycle){
        g << "Ciclu negativ!\n";
    } else {
        for(llong i = 2; i <= n; i++)
            g<<dist[i]<<" ";
    }


}

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

    G.resize(n + 1);
    dist.resize(n + 1, LLONG_MAX);
    int x, y, c;
    while(f>>x>>y>>c){

       G[x].push_back(make_pair(y, c));
    }
    Bellman_Ford(1);



    return 0;
}