#include <fstream>
#include <vector>
#include <list>
#include <limits>
#include <queue>

using namespace std;

constexpr int INF = 1 << 30;

int main()
{
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");

    int n, m;
    in >> n >> m;

    vector<list<pair<int, int> > >adj(n+1);

    int x, y, c;
    for (int i = 0; i < m; ++i)
    {
        in >> x >> y >> c;
        adj[x].push_back(make_pair(y, c));
    }

    vector<int> dist(n + 1, INF);
    dist[1] = 0;
    bool negative_cycle = false;

    queue<int> q;
    vector<bool> in_q(n+1, false);
    vector<int> cnt_in_q(n+1, 0);
    
    q.push(1);
    in_q[1] = true;
    cnt_in_q[1] = 1;
    while (!q.empty() && !negative_cycle)
    {
        int source = q.front();
        q.pop();
        in_q[source] = false;

        for (auto edge : adj[source])
        {
            int dest = edge.first;
            int cost = edge.second;

            if (dist[dest] > dist[source] + cost) 
            {
                dist[dest] = dist[source] + cost;
                if (!in_q[dest])
                {
                    if (cnt_in_q[dest] > n)
                    {
                        negative_cycle = true;
                    }
                    else 
                    {
                        q.push(dest);
                        in_q[dest] = true;
                        ++cnt_in_q[dest];
                    }
                }
            }
        }
    }

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

    in.close();
    out.close();
}