#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#include <string.h>

using namespace std;

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

int n,m;
int updates[50005],dist[50005]={INT_MAX};
vector<pair<int, int> >adj[250000];
bool esteQ[50005]={0};

queue<int>Q;

void citire(){
    f>>n>>m;
    int x, y, c;
    for(int i=0; i<m; i++){
        f>>x>>y>>c;
        adj[x-1].emplace_back(y-1,c);
    }
    memset(dist,11, sizeof(dist));
}

void rezolvare(){
    dist[0]=0;
    Q.push(0);
    esteQ[0]=true;
    while(!Q.empty()){
        int nod=Q.front();
        Q.pop();
        esteQ[nod]=false;
        for(auto &v : adj[nod]){
            if(updates[v.first]==n){
                g<<"Ciclu negativ!";
                return;
            }
            if(dist[nod]+v.second < dist[v.first]){
                dist[v.first]=dist[nod] +v.second;
                if(!esteQ[v.first]){
                    esteQ[v.first]= true;
                    Q.push(v.first);
                    updates[v.first]++;
                }
            }
        }
    }
    for(int i=1; i<n; i++)
        g<<dist[i]<<" ";
}

int main() {
    citire();
    rezolvare();

    return 0;
}