#include <bits/stdc++.h>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m;
vector<pair<int,int>> lista[50005];
int viz[50005],dp[50005];
void citire(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,c;
        fin>>x>>y>>c;
        lista[x].push_back({y,c});
    }
}
bool bellman_ford(int start){
    queue<int> q;
    for(int i=1;i<=n;i++)
        dp[i]=INT_MAX,viz[i]=0;
    dp[start]=0;
    q.push(start);
    ///viz[start]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        viz[x]++;
        if(viz[x]==n)return true;
        for(auto vecin:lista[x]){
                int cost=dp[x]+vecin.second;
            if(cost<dp[vecin.first])
            {
                dp[vecin.first]=cost;
                q.push(vecin.first);
            }
        }
    }
    return false;
}
int main()
{
    citire();
    if(bellman_ford(1))fout<<"Ciclu negativ!";
    else
        if(!bellman_ford(1))
            for(int i=2;i<=n;i++)
                fout<<dp[i]<<" ";
    return 0;
}