#include <bits/stdc++.h>
#ifdef LOCAL
#define in cin
#define out cout
#endif

using namespace std;

#ifndef LOCAL
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
#endif

const int nmax = 5e4 + 5;
const int inf = 2e9;
int n, m;

vector<pair<int, int>> adj[nmax];
int dist[nmax];
bool inq[nmax];
int cnt[nmax];

bool bellmanford(int start = 1)
{
    for (int i = 1; i <=n;i++)dist[i]=inf;
        queue<int> q;
    q.push(start);
    inq[start] = 1;
    dist[start]=0;
    cnt[start]++;
    while (!q.empty())
    {
        int nod = q.front();
        q.pop();
        inq[nod] = 0;
        for (auto i : adj[nod])
        {
            if (dist[i.first]>dist[nod]+i.second)
            {
                if(!inq[i.first])
                {
                    inq[i.first]=1;
                    q.push(i.first);
                    cnt[i.first]++;
                    if(cnt[i.first]>n)return 0;
                }
                dist[i.first]=dist[nod]+i.second;
            }
        }
    }
    return 1;
}

int main()
{
    in >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        in >> a >> b >> c;
        adj[a].push_back({b, c});
    }

    if(bellmanford())
    {
        for(int i=2;i<=n;i++)out<<dist[i]<<' ';
    }
    else
    {
        out<<"Ciclu negativ!";
    }
}