#include <bits/stdc++.h>
using namespace std;

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

const int INF = 0x3f3f3f3f;
const int NMax = 50005;

vector <pair <int, int> > G[NMax];
queue <int> Q;
int dist[NMax], vertices, edges, times[NMax];
bool in_queue[NMax], negative_cycle = false;

int main() {
    in >> vertices >> edges;

    for (int i = 1; i <= edges; ++ i) {
        int from, to, cost;

        in >> from >> to >> cost;
        G[from].push_back (make_pair (to, cost));
    }

    memset (dist, INF, sizeof dist);

    dist[1] = 0;
    Q.push (1);
    in_queue[1] = true;

    while (!Q.empty() && !negative_cycle) {
        int crt_node = Q.front ();
        Q.pop ();
        in_queue[crt_node] = false;

        for (auto &it : G[crt_node]) {
            int to = it.first;
            int cost = it.second;

            if (dist[to] > dist[crt_node] + cost) {
                dist[to] = dist[crt_node] + cost;

                if (!in_queue[to]) {
                    if (times[to] > vertices) {
                        negative_cycle = true;
                    }
                    else {
                        Q.push (to);
                        in_queue[to] = true;
                        times[to] ++ ;
                    }
                }
            }
        }
    }

    if(negative_cycle) {
        out << "Ciclu negativ!";
    }
    else {
        for (int i = 2; i <= vertices; ++ i) {
            out << dist[i] << " ";
        }
    }

    return 0;
}