#include <iostream>
#include <fstream>
#include <climits>
#include <queue>
#include <vector>
#include <utility>
#define VMAX 50000

using namespace std;

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

vector < pair <int,int> > adj[VMAX];
int V, E, x, y, u, v, cost, src;
queue <int> q;
int nr[VMAX];
int d[VMAX];
bool inQueue[VMAX];

int main()
{
    fin >> V >> E;
    src = 1;

    while (E--)
    {
        fin >> x >> y >> cost;
        adj[x - 1].push_back({y - 1, cost});
    }

    --src;

    for (int i = 0; i < V; ++i)
        d[i] = INT_MAX;

    d[src] = 0;
    q.push(src);
    inQueue[src] = true;

    while (!q.empty())
    {
        u = q.front();
        q.pop();
        ++nr[u];
        if (nr[u] >= V)
        {
            fout << "Ciclu negativ!";
            return 0;
        }
        for (auto w : adj[u])
        {
            v = w.first;
            cost = w.second;
            if (d[u] != INT_MAX && d[u] + cost < d[v])
            {
                d[v] = d[u] + cost;
                if (!inQueue[v]) q.push(v);
            }
        }
    }

    for (int i = 1; i < V; ++i)
        fout << d[i] << " ";

    fin.close();
    fout.close();
    return 0;
}