#include <cstdio>
#include <vector>
#include <algorithm>
#define inf 1000000000

using namespace std;

struct Muchie
{
    int a, b;
    int cost;
} vm[250000];
int n, m;

int dist[50000];
int pr[50000];

int main()
{
    int i, j;
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i = 0; i < m; i++)
    {
        scanf("%d%d%d", &vm[i].a, &vm[i].b, &vm[i].cost);
        vm[i].a--; vm[i].b--;
    }
    for(i = 1; i < n; i++)
        dist[i] = inf;
    for(i = 0; i < n - 1; i++)
    {
        for(j = 0; j < m; j++)
        {
            if(dist[vm[j].b] > dist[vm[j].a] + vm[j].cost)
            {
                dist[vm[j].b] = dist[vm[j].a] + vm[j].cost;
                pr[vm[j].b] = vm[j].a;
            }
        }
    }

    for(j = 0; j < m; j++)
    {
        if(dist[vm[j].b] > dist[vm[j].a] + vm[j].cost)
        {
            printf("Ciclu negativ!");
            return 0;
        }
    }

    for(i = 1; i < n; i++)
        printf("%d ", dist[i]);

    return 0;
}