#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3F3F3F3F;

int n, m;
vector<vector<pair<int,int>>>adj;
vector<int>dist;
vector<int>cnt;
vector<bool>inQueue;
bool negative_cycle = false;

void PFA(int start)
{
    queue<int>q;
    dist[start] = 0;

    q.push(start);
    inQueue[start] = true;

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


        for(int vecin : adj[nod])
        {
            int v = vecin.first;
            int w = vecin.second;
            if(dist[nod] + w  < dist[v])
            {
                cnt[v]++;
                if(cnt[v] == n)
                {
                    negative_cycle = true;
                    return;
                }

                dist[v] = dist[u] + w;
                if(!inQueue[])
                {
                    q.push(u);
                    inQueue[u] = true;
                }

            }
        }
    }
}

int main()
{
freopen("bellmanford.in", "r", stdin);
freopen("bellmanford.out", "w", stdout);
scanf("%d %d", &n, &m);
adj.resize(n+1);
for(int i = 1; i <= m; i++)
{
    int x, y, c;
    scanf("%d %d %d", &x, &y, &c);
    adj[x].emplace_back(y, c);
}
dist.assign(n+1, INF);
cnt.assign(n+1, 0);
inQueue.resize(n+1);
PFA(1);
if(!negative_cycle)
{
    for(int i = 2; i <= n; i++)
        printf("%d ", dist[i]);
}
else
{
    printf("Ciclu negativ!");
}
    return 0;
}