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

using namespace std;

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

int nodeNum, edgeNum, node1, node2, cost;
int dist[DIM], frequency[DIM];

vector<pair<int, int> > graph[DIM];

queue<int> q;

bitset<DIM> visited;

bool bellmanford(){
    for(int cnt = 2; cnt <= nodeNum; ++ cnt){
        dist[cnt] = INF;
    }
    q.push(1);
    visited[1] = true;
    frequency[1] = 1;

    while(!q.empty()){
        int currentNode = q.front();
        visited[currentNode] = false;
        q.pop();
        for(auto nextNode : graph[currentNode]){
            if(dist[nextNode.first] > dist[currentNode] + nextNode.second){
                ++ frequency[nextNode.first];
                if(frequency[nextNode.first] == nodeNum)
                    return true;
                dist[nextNode.first] = dist[currentNode] + nextNode.second;
                if(!visited[nextNode.first])
                    q.push(nextNode.first);
            }
        }
    }

    return false;
}

int main()
{
    in>>nodeNum>>edgeNum;

    for(int edgeCnt = 1; edgeCnt <= edgeNum; ++ edgeCnt){
        in>>node1>>node2>>cost;
        graph[node1].push_back(make_pair(node2, cost));
    }

    if(bellmanford()){
        out<<"Ciclu negativ!";
        return 0;
    }

    for(int nodeCnt = 2; nodeCnt <= nodeNum; ++ nodeCnt){
        out<<dist[nodeCnt]<<" ";
    }

    return 0;
}