#include <bits/stdc++.h>
#define INF 2e9

using namespace std;

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

int n, m, cnt[50005], dp[50005];
vector <pair<int, int> > a[50005];
queue <int> Q;

int main()
{
    int i, x, y, cost, isCycle;
    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        a[x].push_back({ cost, y });
    }

    for (i = 1; i <= n; i++)
        dp[i] = INF;
    dp[1] = 0;
    Q.push(1);
    cnt[1] = 1;
    isCycle = 0;
    while (!Q.empty() and !isCycle)
    {
        x = Q.front();
        Q.pop();
        for (auto w : a[x])
        {
            if (dp[w.second] > dp[x] + w.first)
            {              
                cnt[w.second]++;
                if (cnt[w.second] > n)
                {
                    isCycle = 1;
                    break;
                }
                dp[w.second] = dp[x] + w.first;
                Q.push(w.second);
            }

        }
    }
    if (isCycle == 1)
        fout << "Ciclu negativ!\n";
    else
        for (i = 2; i <= n; i++)
            fout << dp[i] << " ";

    return 0;
}