#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;
int n, m;
int dist[50005], utilizari_nod[50005];
vector < pair <int, int> > graf[50005];

void bellman_ford()
{
    deque <int> coada;
    bitset <50005> in_coada;
    coada.clear();
    in_coada.reset();
    memset(dist, inf, sizeof dist);
    coada.push_back(1);
    in_coada[1] = true;
    dist[1] = 0;
    while (!coada.empty())
    {
        int nod = coada.front();
        coada.pop_front();
        in_coada[nod] = false;
        for (const auto &it: graf[nod])
        {
            int next_nod = it.first, next_dist = it.second;
            if (dist[next_nod] > dist[nod] + next_dist)
            {
                dist[next_nod] = dist[nod] + next_dist;
                if (!in_coada[next_nod])
                {
                    coada.push_back(next_nod);
                    in_coada[next_nod] = true;
                    utilizari_nod[next_nod]++;
                    if (utilizari_nod[next_nod] > n - 1)
                    { printf("Ciclu negativ!"); exit(0);}
                }
            }
        }
    }
    for (int i = 2; i <= n; i++)
        printf("%d ", dist[i]);
}

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 1, a, b, cost; i <= n; i++)
        scanf("%d %d %d", &a, &b, &cost),
        graf[a].push_back(make_pair(b, cost));
    bellman_ford();
}