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

const int INF = 0x3F3F3F3F;

int n, m;
vector<pair<int,int>>adj[50001];
vector<int>dist;
int cnt[50001];
bool inQueue[50001];
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(auto 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[nod] + w;
                if(!inQueue[v])
                {
                    q.push(v);
                    inQueue[v] = true;
                }

            }
        }
    }
}

int main()
{
freopen("bellmanford.in", "r", stdin);
freopen("bellmanford.out", "w", stdout);
scanf("%d %d", &n, &m);
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);
PFA(1);
if(!negative_cycle)
{
    for(int i = 2; i <= n; i++)
        printf("%d ", dist[i]);
}
else
{
    printf("Ciclu negativ!");
}
    return 0;
}