#include <bits/stdc++.h>

using namespace std;

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

int N, M;

struct Edge
{
    int node, cost;
};

vector<vector<Edge>> adj;

void Citire()
{
    fin >> N >> M;
    adj.resize(N + 1);
    while (M--)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        adj[x].push_back( { y, cost } );
    }
}

constexpr int oo = 2000000005;
vector<int> dp;
vector<int> cnt;
vector<bool> enqueue;
queue<int> q;

void SPFA()
{
    dp.resize(N + 1, oo);
    cnt.resize(N + 1, 0);
    enqueue.resize(N + 1, false);

    dp[1] = 0;
    q.push(1);
    enqueue[1] = true;

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        enqueue[u] = false;

        for (auto e : adj[u])
            if (dp[e.node] > dp[u] + e.cost)
            {
                dp[e.node] = dp[u] + e.cost;
                if (!enqueue[e.node])
                {
                    q.push(e.node);
                    enqueue[e.node] = true;
                    cnt[e.node]++;
                    if (cnt[e.node] == N)
                    {
                        fout << "Ciclu negativ!\n";
                        return;
                    }
                }
            }

    }

    for (int i = 2; i <= N; i++)
        fout << dp[i] << ' ';
    fout << '\n';
}

int main()
{
    Citire();
    SPFA();

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