#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define O 50010
#define oo 2147483627
using namespace std;

vector <pair <int, int> > G[O];
queue <int> q;
int dist[O], vfciclu[O];
int N, M, k;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

void citire()
{
    in >> N >> M;
    int x, y, c;
    for(int i = 1; i <= M; i++)
    {
        in >> x >> y >> c;
        G[x].emplace_back(y, c);
    }
}

int bellmanford(int z)
{
    int cost, nod;
    for(int i = 2; i <= N; i++)
        dist[i] = oo;

    q.push(z);
    dist[z] = 0;

    while(!q.empty())
    {
        nod = q.front();
        q.pop();
        vfciclu[nod]++;

        if(vfciclu[nod] == N)
            return 1;

        for(int i = 0; i < G[nod].size(); i++)
            if(dist[G[nod][i].first] > dist[nod] + G[nod][i].second)
            {
                q.push(G[nod][i].first);
                dist[G[nod][i].first] = dist[nod] + G[nod][i].second;
            }

    }
    return 0;
}

int main()
{
    citire();

    if(bellmanford(1))
        out << "Ciclu negativ!";
    else
        for(int i = 2; i <= N; i++)
            out << dist[i] << ' ';

    return 0;
}