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

#define pii pair <int, int>
#define f first
#define s second

using namespace std;

vector <pii> v[50010];
queue <int> q;
bool ap[50010];
int t[50010], nr[50010];

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

    int n, m;
    scanf ("%d %d", &n, &m);

    for (int i = 2; i <= n; ++i)
        t[i] = 2000000000;

    for (int i = 1; i <= m; ++i)
    {
        int x, y, cost;
        scanf ("%d %d %d", &x, &y, &cost);
        v[x].push_back ({y, cost});
    }

    nr[1] = 1;
    q.push (1);
    for (; !q.empty ();)
    {
        int x = q.front ();
        q.pop ();

        ap[x] = false;

        for (auto &it : v[x])
            if (t[it.f] > t[x] + it.s)
            {
                t[it.f] = t[x] + it.s;
                if (!ap[it.f]) q.push (it.f), ap[it.f] = true;
                ++nr[it.f];
                if (nr[it.f] >= n)
                {
                    printf ("Ciclu negativ!\n");
                    return 0;
                }
            }
    }

    for (int i = 2; i <= n; ++i)
        printf ("%d ", t[i]);

    printf ("\n");

    return 0;
}