#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;
bool negative_cycle = false;

struct Compare
{
    bool operator()(const pair<int, int>& p1, const pair <int, int>& p2) const
    {
        return p1.second > p2.second;
    }
};

void PFA(int start)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare>pq;
    dist[start] = 0;

    pq.emplace(start, 0);
    while(!pq.empty())
    {
        auto top = pq.top();
        pq.pop();

        int u = top.first;
        int d = top.second;

        if(dist[u] < d)
            continue;

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

                dist[v] = dist[u] + w;
                pq.emplace(v, dist[v]);

            }
        }
    }
}

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);
PFA(1);
if(!negative_cycle)
{
    for(int i = 2; i <= n; i++)
        printf("%d ", dist[i]);
}
else
{
    printf("Ciclu negativ!");
}
    return 0;
}