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

using namespace std;

#define FIN "bellmanford.in"
#define FOUT "bellmanford.out"

#define MAXN 50001
#define INF 50000001

int N, M;
int A[MAXN], B[MAXN], D[MAXN];

vector < pair<int, int> > V[MAXN];
queue <int> Q;

int main()
{
    int i, j, x, y;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d%d", &N, &M);

    for (i = 1; i <= M; ++ i)
    {
        scanf("%d%d%d", &x, &y, &j);

        V[x].push_back(make_pair(y, j));
    }

    Q.push(1);
    A[1] = B[1] = 1;

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

    while (!Q.empty())
    {
        x = Q.front(); Q.pop();
        A[x] = 0;

        for (j = 0; j < V[x].size(); ++ j)
            if (D[x] + V[x][j].second < D[V[x][j].first])
            {
                D[V[x][j].first] = D[x] + V[x][j].second;

                if (A[V[x][j].first] < N && !B[V[x][j].first])
                {
                    Q.push(V[x][j].first);
                    ++ A[V[x][j].first]; B[V[x][j].first] = 1;
                }
            }
    }

    for (i = 1; i <= N; ++ i)
        for (j = 0; j < V[i].size(); ++ j)
            if (D[i] + V[i][j].second < D[V[i][j].first])
            {
                printf("Ciclu negativ!\n");
                return 0;
            }
    for (i = 2; i <= N; ++ i)
        printf("%d ", D[i]);
    printf("\n");
}