#include <fstream>
#include <vector>
#include <queue>

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

const int N = 5e4+1;
const int M = 25e4+1;
const long long INF = 25e7+1; 
int n, m, cost[M];
std::vector<std::pair<int,int>> g[N];
int cnt[N];
long long minCost[N];
bool inQueue[N];

bool negative_cycle(){
    std::queue<int> q;
    std::fill(minCost+1, minCost+n+1, INF);
    
    minCost[1] = 0;
    q.push(1);
    inQueue[1] = true;
    while(!q.empty()){
        int currNode = q.front();
        q.pop();
        inQueue[currNode] = false;
        for(auto branch : g[currNode]){
            int node = branch.first;
            int len  = cost[branch.second];
            if(minCost[currNode] + len < minCost[node]){
                minCost[node] = minCost[currNode] + len;
                if(!inQueue[node]){
                    ++cnt[node];
                    if(cnt[node] > n)
                        return true;
                    q.push(node);
                    inQueue[node] = true;
                }
            }
        }
    }
    return false;
}

int main(){
    in>>n>>m;
    for(int i = 0; i < m; ++i){
        int u, v;
        in >> u >> v >> cost[i];
        g[u].push_back({v, i});
    }
    if(negative_cycle()){
        out << "Ciclu negativ!";
        return 0;
    }
    for(int i = 2; i <= n; ++ i){
        out << minCost[i] << ' ';
    }  
}