#include <iostream>
#include <fstream>
using namespace std;
ifstream ka("bellmanford.in");
ofstream ki("bellmanford.out");
const int N_MAX = 50000;
const int M_MAX = 250000;
int n, m, x, y, c, distanta[N_MAX + 1];
struct muchie
{
    int x, y, c;
}muchii[M_MAX + 1];

int main()
{
    ka >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        muchie muchie;
        ka >> muchie.x >> muchie.y >> muchie.c;
        muchii[++muchii[0].x] = muchie;
    }
    for(int i = 2; i <= n; i++)
        distanta[i] = 0x7fffffff;
    bool schimbat = true;
    for(int i = 1; i <= n && schimbat; i++)
    {
        schimbat = false;
        for(int j = 1; j <= muchii[0].x; j++)
        {
            if(distanta[muchii[j].x] + muchii[j].c < distanta[muchii[j].y])
            {
                distanta[muchii[j].y] = distanta[muchii[j].x] + muchii[j].c;
                schimbat = true;
            }
        }
    }
    schimbat = false;
    for(int j = 1; j <= muchii[0].x; j++)
    {
        if(distanta[muchii[j].x] + muchii[j].c < distanta[muchii[j].y])
        {
            distanta[muchii[j].y] = distanta[muchii[j].x] + muchii[j].c;
            schimbat = true;
        }
    }
    if(schimbat)
        ki << "Ciclu negativ!";
    else
        for(int i = 2; i <= n; i++)
            ki << distanta[i] << " ";
}