#include <queue>
#include <tuple>
#include <vector>
#include <fstream>

using namespace std;

const int NMAX = 50010;
const int INF = (1 << 30);
int nodes, edges;
vector <pair <int, int> > graph[NMAX];
int dist[NMAX],  cntinq[NMAX];
bool inq[NMAX];

int main()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    fin >> nodes >> edges;
    for (int i = 1;i <= edges;++i)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        graph[x].push_back(make_pair(y, cost));
    }
    for (int i = 1;i <= nodes;++i)
        dist[i] = INF;
    dist[1] = 0;
    queue <int> q;
    q.push(1);
    bool negativeCycle = false;
    while (!q.empty() && !negativeCycle)
    {
        int node = q.front();
        q.pop();
        inq[node] = false;
        for (auto &x : graph[node])
        {
            int next, cost;
            tie(next, cost) = x;
            if (dist[next] > dist[node] + cost)
            {
                dist[next] = dist[node] + cost;
                if (cntinq[next] > nodes)
                    negativeCycle = true;
                if (inq[next] == false)
                {
                    inq[next] = true;
                    ++cntinq[next];
                    q.push(next);
                }
            }
        }
    }
    if (negativeCycle)
        fout << "Ciclu negativ!\n";
    else
        for (int i = 2;i <= nodes;++i, fout << " ")
            fout << dist[i];
    fin.close();
    fout.close();
    return 0;
}