#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define MAXN 50005
#define inf 0x7fffffff

using namespace std;

struct vecin
{
    int y, c;
};

queue<int> q;
vector<vecin> v[MAXN];
int dmin[MAXN], viz[MAXN], cont[MAXN], n, m;

void ford()
{
    q.push(1);
    while (!q.empty())
    {
        int top = q.front();
        q.pop();
        viz[top] = 0;
        for (int i = 0; i < v[top].size(); i++)
            if (dmin[v[top][i].y] > dmin[top] + v[top][i].c)
            {
               dmin[v[top][i].y] = dmin[top] + v[top][i].c;
               if (!viz[v[top][i].y])
               {
                   viz[v[top][i].y] = 1;
                   cont[v[top][i].y]++;
                   if (cont[v[top][i].y] > n)
                   {
                       printf("Ciclu negativ!");
                       return;
                   }
                   q.push(v[top][i].y);
               }
            }
    }
    for (int i = 2; i <= n; i++)
        printf("%d ", dmin[i]);
}

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

    scanf("%d %d", &n, &m);
    int x, y, c;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &x, &y, &c);
        v[x].push_back({y, c});
    }
    for (int i = 2; i <= n; i++)
        dmin[i] = inf;
    ford();
    return 0;
}