#include <bits/stdc++.h>

using namespace std;

const int NMAX = 50005;

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

int main()
{
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    int n, m, a, b, val;
    cin>>n>>m;

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

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

    bool rez = true;
    int changes = 0;
    for(int i=0; i<m-1; i++)
    {
        changes = 0;
        for(int dr = 1; dr <= n; dr ++)
        {
            for(auto st : adj[dr])
            {
                int cost = st.second, nst = st.first;

                if(save[nst] > save[dr] + cost)
                    save[nst] = save[dr] + cost, changes ++;
            }
        }

        if(changes == 0)
            break;

        if(changes > 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;
}