#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");
queue<int> q;
int n,m,x,y,c;
bool ciclu_negativ_gasit = false;
int nr_introdus_in_coada[50001],distante[50001];
vector<pair<int,int>>adiacenta[50001];
int main()
{
    f >> n >> m;
    for(int i  = 1;i<=m;i++)
    {
        f >> x >> y >> c;
        adiacenta[x].push_back({y,c});
    }

    nr_introdus_in_coada[1] = 1;
    distante[1] = 0;

    for(int i = 2;i<=n;i++)
        distante[i] = INT_MAX;

    q.push(1);
    while(!q.empty() && !ciclu_negativ_gasit)
    {
        int curent = q.front();
        q.pop();

        for(auto i:adiacenta[curent])
        {
            if(nr_introdus_in_coada[i.first] <= n && distante[i.first] > distante[curent] + i.second)
            {
                distante[i.first] = distante[curent] + i.second;
                nr_introdus_in_coada[i.first]++;
                q.push(i.first);
            }
            if(nr_introdus_in_coada[i.first]>n)
            {
                ciclu_negativ_gasit = true;
            }
        }
    }

    if(ciclu_negativ_gasit)
    {
        g<<"Ciclu negativ!";
    }
    else
        for(int i = 2;i<=n;i++)
    {
         g << distante[i]<< " ";
    }

}