#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int NMAX=5e4, inf=1e9;
vector<pair<int,int> > mat[NMAX+5];
vector<int> dist(NMAX+5, inf);
vector<int>cnt(NMAX+5,0);
queue<int> q;
vector<bool> inqueue(NMAX+5);
int n, m;
bool spfa(){
    dist[1]=0;
    q.push(1);
    inqueue[1]=1;
    while(!q.empty()){
        int nod=q.front();
        q.pop();
        inqueue[nod]=0;
        for(auto it:mat[nod]){
            int nod1=it.first, cost1=it.second;
            if(dist[nod1]>dist[nod]+cost1){
                dist[nod1]=dist[nod]+cost1;
                if(inqueue[nod1]==0){
                    q.push(nod1);
                    inqueue[nod1]=1;
                    cnt[nod1]++;
                    if(cnt[nod1]>n){
                        return 0;
                    }
                }
            }
        }
    }
    return 1;
}
int main(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x, y, z;
        fin>>x>>y>>z;
        mat[x].push_back({y,z});
    }
    bool ans=spfa();
    if(ans){
        for(int i=2;i<=n;i++){
            fout<<dist[i]<<' ';
        }
    }else{
        fout<<"Ciclu negativ!";
    }
}