#include <bits/stdc++.h>

using namespace std;

struct pereche{
    int y, cost;
};

const int N = 50005;
bitset<N>in_queue;
queue<int>q;
vector<pereche>v[N];
int dp[N];
int cnt[N];
bool ok = true;

void init(int n){
    for(int i=2;i<=n;i++){
        dp[i]=1<<30;
    }
}

void bfs(int n){
    q.push(1);
    dp[1]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(auto y:v[x]){
            if(dp[y.y]>dp[x]+y.cost){
                dp[y.y]=dp[x]+y.cost;
                if(!in_queue[y.y]){
                    in_queue[y.y] = true;
                    cnt[y.y]++;
                    if(cnt[y.y]>n-1){
                        ok = false;
                        return ;
                    }
                    q.push(y.y);
                }
            }
        }
        in_queue[x] = false;
    }
}

int main() {

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

    int n,m;
    in>>n>>m;
    int x,y,cost;
    while(m--){
        in>>x>>y>>cost;
        pereche w;
        w.y=y;
        w.cost=cost;
        v[x].push_back(w);
    }
    init(n);
    bfs(n);
    if(ok){
        for(int i=2;i<=n;i++){
            out<<dp[i]<<' ';
        }
    }
    else{
        out<<"Ciclu negativ!";
    }
    return 0;
}