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

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

const int NMAX=50001;

vector<pair<int, int>> adj[NMAX];
int n, m, id[NMAX], dist[NMAX];
bool cn=false;

int main(){
    fin >> n >> m;
    while(m--){
        int a, b, w;
        fin >> a >> b >> w;
        adj[a].push_back({b, w});
    }
    for(int i=2; i<=n; i++) dist[i]=INT_MAX/2;
    queue<int> q;
    q.push(1);
    while(!q.empty() && !cn){
        int s=q.front(); q.pop();
        for(auto u : adj[s]){
            if(dist[u.first]>dist[s]+u.second){
                if(id[u.first]<=n){
                    dist[u.first]=dist[s]+u.second;
                    q.push(u.first);
                    id[u.first]++;
                }else{
                    cn=true;
                    break;
                }
            }
        }
    }
    if(cn) fout << "Ciclu negativ!";
    else for(int i=2; i<=n; i++) fout << dist[i] << ' ';
}