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

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

const int NMAX = 50000;
const int INF = 0x3f3f3f3f;

int n,m;
vector < pair < int , int > > G[NMAX + 1];
queue < int > q;
int dist[NMAX + 1];
int viz[NMAX + 1];

void read(){
    fin >> n >> m;
    for(int i = 1;i<=m;++i){
        int x,y,c;
        fin >> x >> y >> c;
        G[x].push_back({y,c});
    }
}

void initializare(){
    for(int i = 1;i<=n;++i)
        dist[i] = INF;
    dist[1] = 0;
}


void bellman_ford(){
    q.push(1);
    while(!q.empty()){
        int nodc = q.front();
        q.pop();
        for(auto nbr : G[nodc])
            if(dist[nbr.first] > dist[nodc] + nbr.second){
                dist[nbr.first] = dist[nodc] + nbr.second;
                viz[nbr.first]++;
                q.push(nbr.first);
            }
    }
}

int main(){


    read();
    initializare();
    bellman_ford();
    for(int i = 1;i<=n;++i)
        if(viz[i] > 1 && dist[i] < 0){
            fout << "Ciclu negativ!";
            return 0;
        }
    for(int i = 1;i<n;++i)
        fout << dist[i + 1] << ' ';
    return 0;
}