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

using namespace std;

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

const int INF = 1e9;
const int N = 5e4;
int dp[N + 1], f[N + 1];

struct node
{
    int nod, cost;
    bool operator < (const node &a)const
    {
        return cost > a.cost;
    }
};

vector <node> g[N + 1];

priority_queue <node> pq;

int n, m, x, y, cost;

void bellmanford (int start)
{
    for (int i = 1; i <= n; ++i)
        dp[i] = INF;
    dp[start] = 0;
    pq.push({start, 0});
    while (!pq.empty() && f[pq.top().nod] < n)
    {
        node x = pq.top();
        pq.pop();
        if (x.cost > dp[x.nod])continue;
        for (auto it : g[x.nod])
            if (dp[x.nod] + it.cost < dp[it.nod])
                f[it.nod]++, dp[it.nod] = dp[x.nod] + it.cost, pq.push({it.nod, dp[it.nod]});
    }
    bool ok = 0;
    for (int i = 1; i <= n; ++i)
        ok |= (f[i] >= n);
    if (ok)
    {
        cout << "Ciclu negativ!";
        return;
    }
    for (int i = 2; i <= n; ++i)
        cout << dp[i] << ' ';
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y >> cost;
        g[x].push_back({y, cost});
    }
    bellmanford (1);
    return 0;
}