#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<pair<pair<int, int>, 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;
        q.push({{a, b}, c});
    }

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



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

        int i = q.front().first.first, j = q.front().first.second, cost = q.front().second;

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

        if(save[j] > save[i] + cost)
        {
            save[j] = save[i] + cost, delta ++;
            q.push({{i, j}, cost});
        }


        if(tries % m == 0)
        {
            runs++;
            if(delta == 0 || 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;
}