#include<bits/stdc++.h>
using namespace std;
string name="bellmanford";

ifstream fin(name+".in");
ofstream fout(name+".out");

struct Edge{
    int y,cost;
    Edge(int y=0,int cost=0):y(y),cost(cost){}
};

vector<vector<Edge>> graph = vector<vector<Edge>>(510000);
vector<int>dist = vector<int>(510000,INT_MAX);
vector<bool>viz = vector<bool>(510000, false);
int n,m;


void bf(int start) {
    dist[start] = 0;

    for (int i = 1; i < n; ++i) {
        for (const auto &item: graph[i]) {
            if (dist[i] + item.cost < dist[item.y])
                dist[item.y] = dist[i] + item.cost;
        }

    }
    for(int i=1;i<n;++i){
         for (const auto &item: graph[i]) {
            if(dist[i]+item.cost<dist[item.y])
            {cout<< "Ciclu negativ!";
                exit(0);}
        }
    }

}


int main(){
    fin>>n>>m;

    for(int i=0;i<m;++i){
        int x,y,z;
        fin>>x>>y>>z;
        graph[x].push_back(Edge(y,z));
    }
bf(1);
    for(int i=2;i<=n;i++){
        fout<<dist[i]<<" ";
    }





}