#include <bits/stdc++.h>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
#define cout g
const int INF = INT_MAX;
int main()
{
    int n,m;
    f >> n >> m;
    vector<vector<pair<long long,int>>> v(n+1, vector<pair<long long,int>>());
    vector<long long> d(n+1, INF);
    queue<pair<long long, int>> q;
    vector<int> cnt(n+1, 0);
    for(int i=1; i<=m; i++)
    {
        int x, y;
        long long c;
        f >> x >> y >> c;
        v[x].push_back({y,c});
    }
    d[1]=0;
    q.push({0,1});
    vector<bool> inq(n+1, 0);
    inq[1]=true;
    bool ciclu = false;
    while(!q.empty() && !ciclu)
    {
        int nod;
        long long dist;
        tie(dist,nod)=q.front();
        q.pop();
        inq[nod]=false;
        for(auto vecin:v[nod])
        {
            if(d[vecin.first]>d[nod]+vecin.second)
            {
                d[vecin.first]=d[nod]+vecin.second;
                if(!inq[vecin.first])
                {
                    q.push({d[vecin.first],vecin.first});
                    inq[vecin.first]=true;

                    cnt[vecin.first]++;
                    if(cnt[vecin.first]>=n)
                    {
                        ciclu=true;
                        break;
                    }
                }
            }
        }
    }
    if(ciclu)
        cout << "Ciclu negativ!" << '\n';
    else
    {
        for(int i=2; i<=n; i++)
            cout << d[i] << " ";
    }
}