#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;
vector<pair<pair<int,int>,int>>edges;
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});
        edges.push_back({{x,y},z});
    }
    for(long long i=1;i<=n;i++)d[i]=1e9;
    d[1]=0;
    for(int i=1;i<n;i++){
        for(int j=0;j<m;j++){
            int u=edges[j].first.first;
            int v=edges[j].first.second;
            int cost=edges[j].second;
            if(d[u]!=1e9){
                d[v]=min(d[v],d[u]+cost);
            }
        }
    }
    bool ok=1;
    for(int j=0;j<m;j++){
        int u=edges[j].first.first;
        int v=edges[j].first.second;
        int cost=edges[j].second;
        if(d[v]>d[u]+cost)ok=0;
    }
    if(ok==0)fout<<"Ciclu negativ!\n";
    else for(long long i=2;i<=n;i++)fout << d[i] <<" ";
    return 0;
}