#include <bits/stdc++.h>

using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
const int INF = 1000000;
struct edge
{
    int from,to,cost;
};
vector<edge> edges;
int n,m,dist[100005],pred[100005],node;

int main()
{
    in>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        edge e;
        in>>x>>y>>z;
        e.from = x-1;
        e.to = y-1;
        e.cost = z;
        edges.push_back(e);
    }
    node = 0;
    for(int i=0;i<n;i++){
        dist[i] = INF;
        pred[i] = -1;
    }
    dist[node] = 0;
    for(int i=0;i<n;i++)
        for(auto edge:edges)
            if(dist[edge.to]>dist[edge.from]+edge.cost){
                dist[edge.to] = dist[edge.from]+edge.cost;
                pred[edge.to] = edge.from;
        }
    if(pred[node] == -1)
        for(int i=1;i<n;i++)
            out<<dist[i]<<' ';
    else
        out<<"Ciclu negativ!";

    return 0;
}