#include <bits/stdc++.h>

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
#define inf 1e7
#define mp make_pair
struct ura{
    int first,second;
};
vector<ura> v[50001];
int dp[50001];
deque<int> q;
int ok[50001],cate[50001];
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]=true;
    q.push_back(1);
    ok_ciclu=false;
    while(!q.empty() && ok_ciclu==false){
        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]){
                    ++cate[muchie.first];
                    if(cate[muchie.first]>n-1){
                        ok_ciclu=false;
                        break;
                    }
                    else{
                        ok[muchie.first]=true;
                        q.push_back(muchie.first);
                    }
                }
            }
        }
    }
    if(ok_ciclu==true)
        out<<"Ciclu negativ!";
    else
        for(i=2;i<=n;++i)
            out<<dp[i]<<" ";
    return 0;
    }