#include<bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const long long inf=1<<30;
//vector<vector<pair<long long,pair<long long,bool>>>>adj(2505);
vector<vector<pair<long long,long long>>>adj(50001);
long long d[50001];
bool viz[50001];
long long t[50001],use[50001];
long long n,m,k,s,f;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    fin >>n>>m;
    for(long long i=1;i<=m;i++){
        long long x,y,z;
        fin >> x >> y >> z;
        //if(z>=0) adj[x].push_back({y,{-z,1}});
        //else adj[x].push_back({y,{z,0}});
        adj[x].push_back({y,z});
    }
    for(long long i=1;i<=n;i++)d[i]=1e9;
    d[1]=0;
    queue<long long>coada;
    coada.push(1);
    while(!coada.empty()){
        long long nod=coada.front();
        coada.pop();
        use[nod]++;
        if(use[nod]==n){
            cout << "Ciclu negativ!";
            return 0;
        }
        for(auto it: adj[nod]){
            if(d[it.first]>d[nod]+it.second){
                d[it.first]=d[nod]+it.second;
                coada.push(it.first);
            }
        }
    }
    for(long long i=2;i<=n;i++)fout << d[i] <<" ";
    return 0;
}