#include <bits/stdc++.h>

using namespace std;

#define inf 2e9
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
struct ura{
    int first,second;
};
vector<ura> v[50001];
deque<int> q;
int ok[50001],dp[50001],cate[50001];

int main()
{
    int n,m,i,first,nod,nod1,cost,x,y,k;
    in>>n>>m;
    for(i=1;i<=m;++i)
    {
        in>>x>>y>>cost;
        v[x].push_back({y,cost});
    }
    bool ok_ciclu=false;
    for(i=1;i<=n;++i)
        dp[i]=inf;
    first=1;
    q.push_back(first);
    dp[first]=0;
    ok[first]=1;
    while(!q.empty() && !ok_ciclu){
        nod=q.front();
        ok[nod]=0;
        q.pop_front();
        for(k=0;k<v[nod].size();++k)
        {
            nod1=v[nod][k].first;
            cost=v[nod][k].second;
            if(dp[nod]+cost<dp[nod1]){
                dp[nod1]=dp[nod]+cost;
                if(!ok[nod1]){
                    ++cate[nod1];
                    if(cate[nod1]>=n)
                    {
                        ok_ciclu=1;
                        break;
                    }
                    else
                    {
                        ok[nod1]=1;
                        q.push_back(nod1);
                    }
                }
            }
        }
    }
    if(ok_ciclu==true)
        out<<"Ciclu negativ!";
    else
    {
        for(i=2;i<=n;++i)
            out<<dp[i]<<" ";
    }
    return 0;
}