#include <iostream>
#include <vector>
#include <queue>

#define NMAX 50005
#define INF ((1 << 30) - 1)

using namespace std;

typedef pair<int, int> pii;

int n, m, ans[NMAX], nrviz[NMAX];
bool cicluNeg;
vector<pii> adj[NMAX];
queue<int> q;

void bellmanFord() {
    ans[1] = 0;
    q.push(1);

    while(!q.empty() && !cicluNeg) {
        const int crt = q.front();
        q.pop();

        for(const auto &el : adj[crt]) {
            const int vecin = el.first, cost = el.second;
            if(ans[vecin] > ans[crt] + cost) {
                ans[vecin] = ans[crt] + cost;
                if(nrviz[vecin] > n) cicluNeg = 1;
                else {
                    ++nrviz[vecin];
                    q.push(vecin);
                }
            }
        }
    }
}

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
        ans[i] = INF;
    for(int x, y, z; m; --m) {
        scanf("%d%d%d", &x, &y, &z);
        adj[x].push_back({y, z});
    }
    bellmanFord();
    if(cicluNeg) printf("Ciclu negativ!");
    else {
        for(int i = 2; i <= n; ++i)
            printf("%d ", ans[i]);
    }
    return 0;
}