#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;
        memset(dist, inf, sizeof dist);
        coada.push_back(1);
        dist[1] = 0;
        while (!coada.empty())
        {
            int nod = coada.front();
            coada.pop_front();

            if (utilizari_nod[nod] >= n)
            { printf("Ciclu negativ!"); exit(0);}

            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;
                    coada.push_back(next_nod);
                    utilizari_nod[next_nod]++;
                }
            }
        }
        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 <= m; i++)
            scanf("%d %d %d", &a, &b, &cost),
            graf[a].push_back(make_pair(b, cost));
        bellman_ford();
    }