#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],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;

    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;

    if(dist[0] != 0)
        for(int i=1;i<n;i++)
            out<<dist[i]<<' ';
    else
        out<<"Ciclu negativ!";

    return 0;
}