#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;

    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]<< " ";

}