#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>

#define MAXN 50005
#define inf 0x14ffffffffffffff

using namespace std;

struct Nod
{
    int val, cost;
    Nod(int _val, int _cost)
    {
        val = _val;
        cost = _cost;
    }
};
queue<int> q;
vector<Nod> vec[MAXN];
bitset<MAXN> inq;
long long best[MAXN];
int gotBetter[MAXN];
int n, m;

void citire()
{
    int x, y, c;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &x, &y, &c);
        vec[x].push_back(Nod(y, c));
    }
    for (int i = 2; i <= n; i++)
        best[i] = inf;
}

void sol()
{
    q.push(1);
    best[1] = 0;
    inq[1] = 1;
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        inq[nod] = 0;
        for (int i = 0; i < vec[nod].size(); i++)
        {
            if (best[nod] + vec[nod][i].cost < best[vec[nod][i].val])
            {
                best[vec[nod][i].val] = best[nod] + vec[nod][i].cost;
                if (++gotBetter[vec[nod][i].val] >= n)
                {
                    printf("Ciclu negativ!");
                    return;
                }

                if (!inq[vec[nod][i].val])
                {
                    inq[vec[nod][i].val] = 1;
                    q.push(vec[nod][i].val);
                }
            }
        }
    }
    for (int i=2; i <= n; i++)
        printf("%d ", best[i]);
}

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    citire();
    sol();
    return 0;
}