#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

#define FILEIN "bellmanford.in"
#define FILEOUT "bellmanford.out"

const int INF  = 0x3f3f3f3f;
const int NMAX = 50002;
vector<pair<int, int> > A[NMAX];
bool in_q[NMAX];
int D[NMAX];
int K[NMAX];
queue<int> Q;

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    int N, M;

    scanf("%d %d", &N, &M);
    for ( int i = 1, x, y, c; i <= M; i++ ) {
        scanf("%d %d %d", &x, &y, &c);
        A[x].push_back(make_pair(y,c));
    }

    for ( int i = 2; i <= N; i++)
        D[i] = INF;

    bool nc = false; int x;
    D[1] = 0;
    Q.push(1);
    in_q[1] = true;
    while (!Q.empty() && !nc) {
        x = Q.front(); Q.pop();
        in_q[x] = false;
        for ( int i = 0; i < A[x].size(); i++) {
            if ( D[x] < INF) {
                if (D[x] + A[x][i].second < D[A[x][i].first]) {
                    D[A[x][i].first] = D[x] + A[x][i].second;
                    if (!in_q[A[x][i].first]) {
                        if (K[A[x][i].first] > N) {
                            nc = true;
                        } else {
                            Q.push(A[x][i].first);
                            in_q[A[x][i].first] = true;
                            K[A[x][i].first]++;
                        }
                    }
                }
            }
        }
    }

    if (!nc) {
        for ( int i = 2; i <= N; i++) {
            printf("%d ", D[i]);
        }
        printf("\n");
    } else printf("Ciclu negativ!\n");

    return 0;
}