#include <bits/stdc++.h>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int inf=1e9+1;

vector<vector<pair<int,int>>>a;
queue<int>q;
vector<int>viz,d;
int n,m,s,t,u;

void bfordulinni(){
    q.push(1);
    for(int i=2;i<=n;i++) d[i]=inf;
    while(!q.empty()){
        int nod=q.front();
        q.pop();
        viz[nod]++;
        if(viz[nod]==n+1){
            fout<<"Ciclu negativ!";
            exit(0);
        }
        for(auto f:a[nod]){
            if(d[nod]+f.second<d[f.first]){
                d[f.first]=d[nod]+f.second;
                q.push(f.first);
            }
        }
    }
}

int main(){
    fin>>n>>m;
    viz.resize(n+1);
    d.resize(n+1);
    a.resize(n+1);
    for(int i=0;i<m;i++){
        fin>>s>>t>>u;
        a[s].push_back({t,u});
    }
    bfordulinni();
    for(int i=2;i<=n;i++) fout<<d[i]<<" ";
    return 0;
}