#include <fstream>
#include <vector>
#include <deque>
#define DIM 50002
#define INF 1e9

using namespace std;

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

int n, m, x, y, cost;
int dp[DIM], visited[DIM];

bool inQueue[DIM];

struct edge{
    int node, cost;
};

vector<edge> graf[DIM];

deque<int> q;

bool bf(int node){
    q.push_back(node);
    visited[node] = 1;
    inQueue[node] = true;
    for(int i = 1; i <= n; ++ i)
        dp[i] = INF;
    dp[node] = 0;
    while(!q.empty()){
        int currentNode = q.front();
        q.pop_front();
        inQueue[currentNode] = false;
        for(auto edg : graf[currentNode]){
            int nextNode = edg.node;
            int cost = edg.cost;
            if(dp[nextNode] > dp[currentNode] + cost){
                dp[nextNode] = dp[currentNode] + cost;
                if(visited[nextNode] == n + 1)
                    return true;
                if(inQueue[nextNode] == false){
                    inQueue[nextNode] = true;
                    ++ visited[nextNode];
                    q.push_back(nextNode);
                }
            }
        }
    }
    return false;
}

int main()
{
    in>>n>>m;
    for(int i = 1; i <= m; ++ i){
        in>>x>>y>>cost;
        graf[x].push_back({y, cost});
    }

    if(bf(1)){
        out<<"Ciclu negativ!";
    }
    else{
        for(int i = 2; i <= n; ++ i)
            out<<dp[i]<<" ";
    }

    return 0;
}