#include <fstream>
#include <utility>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

#define inFile "bellmanford.in"
#define outFile "bellmanford.out"
#define MAX_V 50001
#define MAX_E 250001
#define INF 1<<30

vector < pair<int,int> > adjList[MAX_V];
queue < int > q;
int d[MAX_V];
int nrReplace[MAX_V];

int main() {
    ifstream in(inFile);
    ofstream out(outFile);
    
    int n, m, i, x, y, cost, node, nextNode;
    vector < pair<int,int> > :: iterator it;
    bool hasNegativeCycle = false;
    
    memset(d, INF, sizeof(d));
    
    in >> n >> m;
    for(i = 1; i <= m; i++) {
        in >> x >> y >> cost;
        adjList[x].push_back(make_pair(y, cost));
    }
    
    d[1] = 0;
    nrReplace[1] = 1;
    q.push(1);
    
    while(!q.empty() && !hasNegativeCycle) {
        node = q.front();
        q.pop();
        
        for(it = adjList[node].begin(); it != adjList[node].end(); it++) {
            nextNode = it -> first;
            cost = it -> second;
            
            if(!d[nextNode]) {
                nrReplace[nextNode] = 1;
                d[nextNode] = d[node] + cost;
                q.push(nextNode);
            }
            else if(d[nextNode] > d[node] + cost) {
                d[nextNode] = d[node] + cost;
                nrReplace[nextNode]++;
                if(nrReplace[nextNode] >= n) hasNegativeCycle = 1;
                q.push(nextNode);
            }
        }
    }
    
    if(hasNegativeCycle) 
        out << "Ciclu negativ!";
    else 
        for(i = 2; i <= n; i++) {
            out << d[i] << ' ';
        }
    out << '\n';
    
    return 0;
}