#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3")

using namespace std;

const int NMAX = 50005;

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

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    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;
    q.push(1);


    bool rez = true;
    int tries = 0, runs = 0;
    while(!q.empty())
    {
        tries ++;

        int i = q.front();
        q.pop();

        if(save[i] == 1e18)
            continue;

        for(auto x : adj[i])
        {
            if(save[x.first] > save[i] + x.second)
            {
                save[x.first] = save[i] + x.second, delta ++;
                q.push(x.first);
            }
        }

        if(tries % m == 0)
        {
            runs++;
            if(runs == n-1)
                break;

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

            delta = 0;
            tries = 0;
        }
    }

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

    return 0;
}