#include <bits/stdc++.h>

using namespace std;
vector<pair<long long,int>> adj[100000];
int main(){
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    int n,m,inf=1e9;
    fin>>n>>m;
    queue<int> q;
    vector<bool> in_queue(n+1,false);
    vector<long long> dist(n+1,inf);
    vector<int> cnt(n+1,0);
    for(int i =0;i<m;i++){
        int u,v;
        long long w;
        fin>>u>>v>>w;
        adj[u].push_back({w,v});
    }
    dist[1]=0;
    q.push(1);
    in_queue[0]=true;
    while(!q.empty()){
        int u=q.front();
        in_queue[u]=false;
        q.pop();
        for(auto &edge:adj[u]){
            int v=edge.second;
            int w=edge.first;
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                if(!in_queue[v]){
                    q.push(v);
                    in_queue[v]=true;
                    cnt[v]++;
                    if(cnt[v]>=n){
                        fout<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }
    for(int i = 2;i<=n;i++){
        fout<<dist[i]<<" ";
    }
    return 0;
}