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

using namespace std;

#define maxN 50005
#define inf (1 << 30)
#define PB push_back
#define MKP make_pair
#define f first
#define s second

int Cost[maxN], Cont[maxN];
bool Viz[maxN];
vector <pair <int, int> > List[maxN];
queue <int> Q;


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

    int N, M;
    scanf ("%d %d", &N, &M);

    while (M --)
    {
        int x, y, c;
        scanf ("%d %d %d", &x, &y, &c);

        List[x].PB ( MKP (y, c) );
    }

    for (int i = 2; i <= N; ++ i) Cost[i] = inf;

    Q.push (1);
    Cont[1] = 1;
    Viz[1] = true;

    while (! Q.empty ())
    {
        int nod = Q.front();
        Q.pop ();
        Viz[nod] = false;

        for (unsigned int i = 0; i < List[nod].size(); ++ i)
        {
            int nod2 = List[nod][i].f, cost2 = List[nod][i].s;

            if (Cost[nod2] <= Cost[nod] + cost2) continue;

            Cost[nod2] = Cost[nod] + cost2;
            ++ Cont[nod2];

            if (Cont[nod2] > N)
            {
                printf ("Ciclu negativ!");
                return 0;
            }


            if (Viz[nod2]) continue;
            Q.push (nod2);
            Viz[nod2] = true;
        }
    }

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


    return 0;
}