#include <bits/stdc++.h>
#define int long long

using namespace std;

const int NMAX = 50005;

vector<pair<int, int>> adj[NMAX];
int save[NMAX];

signed main()
{
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    int n, m, a, b, c, delta = 0;
    cin>>n>>m;

    for(int i=0; i<m; i++)
    {
        cin>>a>>b>>c;
        adj[a].push_back({b, c});
    }

    for(int i=1; i<=n; i++)
        save[i] = 1e18;
    save[1] = 0;

    bool rez = true;
    for(int i=0; i<m; i++)
    {
        int delta = 0;
        for(int j=1; j<=n; j++)
        {
            if(save[j] == 1e18)
                continue;

            for(auto x : adj[j])
            {
                int next = x.first, cost = x.second;

                if(save[next] > save[j] + cost)
                    save[next] = save[j] + cost, delta ++;
            }
        }

        if(delta == 0)
            break;

        if(delta > 0 && i == m - 1)
            rez = false;
    }

    if(rez == false)
        cout<<"Ciclu negativ!";
    else
    {
        for(int i=2; i<=n; i++)
            cout<<save[i]<<" ";
    }

    return 0;
}