#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,negativ=1;
int vis[50005],dp[50005],cnt[50005];
vector<date>v[50005];
queue<date>q;
void citire(){
    ci>>n>>m;
    date p;
    int x;
    for(int i=1;i<=m;i++){
        ci>>x>>p.nod>>p.cost;
        //cout<<x<<"\n";
        v[x].push_back(p);
    }

}

void bellmanford(){
    for(int i=2;i<=n;i++){
        dp[i]=INF;
    }
    dp[1]=0;
    vis[1]=1;
    cnt[1]=1;
    date w;
    w.nod=1;
    w.cost=0;
    q.push(w);

    while(negativ&&!q.empty()){

        w=q.front();
        q.pop();
        vis[w.nod]=0;
        for(auto i:v[w.nod]){
            if(dp[i.nod]>dp[w.nod]+i.cost){
                dp[i.nod]=dp[w.nod]+i.cost;
                if(!vis[i.nod]){
                    q.push(i);
                    vis[i.nod]=1;
                    cnt[i.nod]++;
                    if(cnt[i.nod]>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;
}