#include <bits/stdc++.h>

using namespace std;

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

struct drumuri{
    int node1,node2,cost;
};

int n,m,x,y,z,drum[50200];
vector <drumuri> edges;

bool bellman()
{
    for(int i=2; i<=n; i++)
        drum[i]=INT_MAX>>1;
    for(int i=1; i<n; i++)
        for(auto u:edges)
            if(drum[u.node1]+u.cost<drum[u.node2])
                drum[u.node2]=drum[u.node1]+u.cost;
    for(auto u:edges)
        if(drum[u.node1]+u.cost<drum[u.node2])
            return 1;
    return 0;
}

int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
        f>>x>>y>>z, edges.push_back({x,y,z});
    if(bellman())
        g<<"Ciclu negativ!";
    else
        for(int i=2; i<=n; i++)
            g<<drum[i]<<' ';
    return 0;
}