#include <fstream>
#include <vector>
#include <climits>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct EDGE{
    int u,v,w;
};
int INF = 300000000;
vector < vector < pair <int,int> > > adjList;
vector < EDGE > edge;
vector <int> dist;

int main()
{
    int n,m,x,y,z;
    fin>>n>>m;
    dist.resize(n + 1,INF);
    adjList.resize(n + 1);
    for(int i = 1;i <= n;i++)
    {
        fin>>x>>y>>z;
        adjList[x].push_back({z,y});
        edge.push_back({x,y,z});
    }
    dist[1] = 0;
    for(int i = 1;i < n;i++)
    {
        for(auto e : edge){
            int a = e.u,b = e.v,c = e.w;
            if(dist[e.v] > dist[e.u] + e.w)
            {
                dist[e.v] = dist[e.u] + e.w;
            }
        }
    }
    for(auto e: edge){
        int a = e.u,b = e.v,c = e.w;
        if(dist[e.v] > dist[e.u] + e.w)
        {
            fout<<"Ciclu negativ!";
            return 0;
        }
    }
    for(int i = 2;i <= n;i++)
        fout<<dist[i]<<" ";
    return 0;
}