#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

struct Muchie
{
    int vecin;
    int cost;
};

vector<Muchie> graf[50005];

long long distanta[50005];
bool inCoada[50005];
int aparitii[50005];

int main()
{
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");

    int N, M;
    in >> N >> M;

    for(int i = 1; i <= M; i++)
    {
        int x, y, c;
        in >> x >> y >> c;

        graf[x].push_back({y, c});
    }

    for(int i = 1; i <= N; i++)
        distanta[i] = INF;

    queue<int> q;

    distanta[1] = 0;
    q.push(1);

    inCoada[1] = true;
    aparitii[1] = 1;

    bool cicluNegativ = false;

    while(!q.empty() && !cicluNegativ)
    {
        int nod = q.front();
        q.pop();

        inCoada[nod] = false;

        for(auto muchie : graf[nod])
        {
            int vecin = muchie.vecin;
            int cost = muchie.cost;

            if(distanta[nod] + cost < distanta[vecin])
            {
                distanta[vecin] = distanta[nod] + cost;

                if(!inCoada[vecin])
                {
                    q.push(vecin);
                    inCoada[vecin] = true;

                    aparitii[vecin]++;

                    if(aparitii[vecin] >= N)
                    {
                        cicluNegativ = true;
                        break;
                    }
                }
            }
        }
    }

    if(cicluNegativ)
    {
        out << "Ciclu negativ!";
        return 0;
    }

    for(int i = 2; i <= N; i++)
        out << distanta[i] << ' ';

    return 0;
}