#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;

ifstream ci("bellmanford.in");
ofstream cou("bellmanford.out");
struct date {
    int nod,cost;
};
int n,m;
int vis[50005],dp[50005];
vector<date>v[50005];
queue<date>q;
void citire(){
    ci>>n>>m;
    date p;
    int x;
    for(int i=1;i<=n;i++){
        ci>>x>>p.nod>>p.cost;
        v[x].push_back(p);
    }
}

void bellmanford(){
    int negativ=1;
    for(int i=2;i<=n;i++){
        dp[i]=INF;
    }
    date w;
    w.nod=1;
    w.cost=0;
    q.push(w);
    while(negativ&&!q.empty()){
        w=q.front();
        q.pop();
        vis[w.nod]++;
        for(auto i:v[w.nod]){
            if(dp[i.nod]>dp[w.nod]+i.cost){
                dp[i.nod]=dp[w.nod]+i.cost;
                i.cost=dp[i.nod];
                q.push(i);

            }
        }
        for(int i=1;i<=n;i++){
            if(vis[i]>n){
                negativ=0;
            }
        }

    }
    if(negativ==0){
        cou<<"Ciclu negativ!";
    }else{
        for(int i=2;i<=n;i++){
            cou<<dp[i]<<" ";
        }
    }


}

int main()
{
    citire();
    bellmanford();
    return 0;
}