#include <bits/stdc++.h>
#define inf 10000000

using namespace std;

struct dijkstra
{
    int nod, cost;
    bool operator<(const dijkstra &a) const
    {
        return cost > a.cost;
    }
};
vector<dijkstra> ad[50001];
priority_queue<dijkstra> pq;
int aparitii[50001], f[50001], m, ok;
void bfs()
{
    int i;
    dijkstra a, aux;
    while (!pq.empty())
    {
        a.nod = pq.top().nod, a.cost = pq.top().cost;
        pq.pop();
        aparitii[a.nod]++;
        if (aparitii[a.nod] <= m && a.cost == f[a.nod])
        {
            for (i = 0; i < ad[a.nod].size(); i++)
            {
                if (f[ad[a.nod][i].nod] > a.cost + ad[a.nod][i].cost)
                {
                    aux.nod = ad[a.nod][i].nod, aux.cost = a.cost + ad[a.nod][i].cost;
                    f[aux.nod] = aux.cost;
                    pq.push(aux);
                }
            }
        }
        else if (aparitii[a.nod] > m)
        {
            ok = 1;
            break;
        }
    }
}

int main()
{
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    int n, i, a, b, c;
    dijkstra aux;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        f[i] = inf;
    for (i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        aux.nod = b, aux.cost = c;
        ad[a].push_back(aux);
    }
    aux.nod = 1, aux.cost = 0;
    f[aux.nod] = aux.cost;
    pq.push(aux);
    bfs();
    if (ok == 1)
        cout << "Ciclu negativ!";
    else
        for (i = 2; i <= n; i++)
            cout << f[i] << " ";
    return 0;
}