#include <bits/stdc++.h>

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
#define inf 2e9
#define mp make_pair
struct ura
{
    int first,second;
};
vector<ura> v[50005];
int dp[50005];
deque<int> q;
int ok[50005],cate[50005];
int main()
{
    int n,m,i,x,y,cost,nod;
    bool ok_ciclu;
    in>>n>>m;
    for(i=1; i<=n; ++i)
        dp[i]=inf;
    for(i=1; i<=m; ++i)
    {
        in>>x>>y>>cost;
        v[x].push_back({y,cost});
    }
    dp[1]=0;
    ok[1]=1;
    q.push_back(1);
    ok_ciclu=false;
    while(!q.empty() && !ok_ciclu)
    {
        nod=q.front();
        ok[nod]=false;
        q.pop_front();
        for(auto muchie : v[nod])
        {
            if(dp[muchie.first]>dp[nod]+muchie.second)
            {
                dp[muchie.first]=dp[nod]+muchie.second;
                if(ok[muchie.first]==0)
                {
                    ++cate[muchie.first];
                    if(cate[muchie.first]>n-1)
                    {
                        ok_ciclu=true;
                        break;
                    }
                    else
                    {
                        ok[muchie.first]=1;
                        q.push_back(muchie.first);
                    }
                }
            }
        }
    }
    if(ok_ciclu==true)
        out<<"Ciclu negativ!";
    else
        for(i=2; i<=n; ++i)
            out<<dp[i]<<" ";
    return 0;
}