#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

fstream f("bellmanford.in",ios::in);
fstream g("bellmanford.out",ios::out);

struct dat
{
    int leg, cost;
};

const int nmax=50010,INF=0x3f3f3f3f;

vector<dat> a[nmax];

int n, m, i, x, negativ, nc, dist[nmax], viz[nmax], nr[nmax];

void citire()
{
    f >> n >> m;
    dat cit;
    for (i = 1;i <= m; i++)
    {
        f >> x >> cit.leg >> cit.cost;
        a[x].push_back(cit);
    }
}

void rezolvare()
{
    memset(dist, INF, sizeof(dist));
    queue <int> q;
    negativ = 0;
    q.push(1);
    viz[1] = 1;
    dist[1] = 0;
    while ((!q.empty()) && (!negativ))
    {
        nc = q.front(); q.pop();
        viz[nc] = 0;
        for (vector <dat>::iterator it = a[nc].begin(); it != a[nc].end(); ++it)
            if (dist[nc] + it->cost < dist[it->leg])
            {
                dist[it->leg] = dist[nc] + it->cost;
                if (!viz[it->leg])
                {
                    if (nr[it->leg] > (n - 1)) negativ = 1;
                    viz[it->leg] = 1;
                    q.push(it->leg);
                    nr[it->leg]++;
                }
            }
    }
    if (negativ) g << "Ciclu negativ!";
    else
    {
        for (i = 2; i <= n; i++)  g << dist[i] << " ";
    }

}

int main()
{
    citire();
    rezolvare();
    return 0;
}