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

#define Nmax 50005
#define INF 0x3f3f3f3f

using namespace std;

int N, M, Viz[Nmax], Cost[Nmax], OK = 1;
vector <pair <int, int> > G[Nmax];
queue <int> Q;

void Citire()
{
    int a, b, c;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= M; ++i)
    {
        scanf("%d %d %d", &a, &b, &c);
        G[a].push_back(make_pair(b, c));
    }
    for (int i = 2; i <= N; ++i)
        Cost[i] = INF;
}

void Bellman_Ford()
{
    int nod;
    Q.push(1);
    Viz[1] = 1;
    while (!Q.empty() && OK)
    {
        nod = Q.front();
        Q.pop();
        for (vector <pair <int, int> > :: iterator it = G[nod].begin(); it != G[nod].end(); ++it)
        {
            if (Cost[it -> first] > Cost[nod] + it -> second && !Viz[it -> first])
            {
                Cost[it -> first] = Cost[nod] + it -> second;
                Q.push(it -> first);
                Viz[it -> first]++;
                if (Viz[it -> first] > N)
                    OK = 0;
            }
        }
    }
}

void Afisare()
{
    if (!OK)
        printf("Ciclu negativ!");
    else
        for (int i = 2; i <= N; ++i)
            if (Cost[i] == INF)
                printf("0 ");
            else
                printf("%d ", Cost[i]);
}

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

    Citire();
    Bellman_Ford();
    Afisare();

    return 0;
}