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

using namespace std;

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

const int INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
int d[50100], nrQ[50100];
bool fr[50100];
vector<vector<pair<int, int>>> adj;
queue<int> q;

bool bellmanFord()
{
    memset(d, INF, sizeof d);

    queue<int> Q;
    Q.push(1);

    d[1] = 0;
    fr[1] = 1;
    nrQ[1] = 1;

    while(!Q.empty())
    {
        int node = Q.front();
        Q.pop();

        fr[node] = 0;

        for(auto it: adj[node])
        {
            int next = it.first;
            int cost = it.second;

            if(d[node] + cost < d[next])
            {
                d[next] = d[node] + cost;

                if(fr[next] == 0)
                {
                    Q.push(next);

                    fr[next] = 1;
                    nrQ[next]++;

                    if(nrQ[next] >= n)
                        return 0;
                }
            }
        }
    }

    return 1;
}

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

    adj.resize(n + 5);

    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        in >> x >> y >> c;

        adj[x].emplace_back(y, c);
    }

    if(bellmanFord() == 0)
        out << "Ciclu negativ!\n";
    else
    {
        for(int i = 2; i <= n; i++)
            out << d[i] << ' ';
        out << '\n';
    }

    return 0;
}