#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#define INF INT_MAX
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,a,b,c;
vector<pair<int,int>>adiacenta[50001];
int distante[50001],fr_bagat_in_coada[50001];
queue<int>q;
int main()
{
    f >> n >> m;
    for(int i = 1;i<=m;i++)
    {
        f >> a >> b >> c;
        adiacenta[a].push_back({b,c});
    }

    distante[1] = 0;
    fr_bagat_in_coada[1] = 1;
    q.push(1);

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

    /// bagam in coada nodul 1, parcurgem vecinii si daca vechea distanta pana la acel vecin este mai mare decat cea de la nodul curent + costul drumului
    /// dintre nodul curent si nodul vecin atunci o modificam si bagam nodul a carei distanta s-a modificat in coada
    /// acest algoritm afla distantele minime dar in aceasta problema costurile ar putea fii si negative ceea ce ar creea un ciclu infinit
    /// deoarece costurile fiind negative se vor reactualiza distantele
    /// asa ca mai folosim un vector care numara de cate ori a fost bagat un nod in coada,iar daca aceasta frecventa ajunge la n+1 inseamna ca ne aflam intr-un ciclu
    while(!q.empty())
    {
        int curent = q.front();
        q.pop();

        for(auto x:adiacenta[curent])
        {
            int vecin = x.first;
            int cost = x.second;

            if(distante[vecin] > distante[curent] + cost)
            {
                distante[vecin] = distante[curent] + cost;
                q.push(vecin);
                fr_bagat_in_coada[vecin] ++;
            }

            if(fr_bagat_in_coada[vecin]>n)
            {
                g << "Ciclu negativ!";
                return 0;
            }

        }
    }

    for(int i = 2;i<=n;i++)
        (distante[i] == INF)?g << "0 ":g << distante[i]<< " ";

}