#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define nmax 50005
#define inf (1<<30)

using namespace std;

int n, m;
int x, y, c;
int cost[nmax];
vector < pair<int, int> > G[nmax];

bool ciclu = false;
int viz[nmax];
bool inQueue[nmax];
queue <int> q;

void bellmanFord()
{
    q.push(1);

    while (!q.empty())
    {
        int nod = q.front();
        q.pop();

        inQueue[nod] = false;

        for (int i = 0; i < G[nod].size(); i++)
            if (cost[nod] + G[nod][i].second < cost[ G[nod][i].first ])
            {
                cost[ G[nod][i].first ] = cost[nod] + G[nod][i].second;

                if (!inQueue[ G[nod][i].first ])
                {
                    inQueue[ G[nod][i].first ] = true;
                    q.push( G[nod][i].first );
                    viz[ G[nod][i].first ]++;
                }

                if ( viz[ G[nod][i].first ] >= n)
                {
                    ciclu = true;
                    return;

                }

            }

    }

}

int main()
{
    ifstream fi("bellmanford.in");
    ofstream fo("bellmanford.out");

    fi >> n >> m;
    for (int i = 1; i <= m; i++)
        fi >> x >> y >> c,
        G[x].push_back(make_pair(y, c));

    for (int i = 2; i <= n; i++)
        cost[i] = inf;
    cost[1] = 0;

    bellmanFord();

    if (ciclu)
        fo << "Ciclu negativ!" << "\n";
    else
        for (int i = 2; i <= n; i++)
            fo << cost[i] << " ";

    fi.close();
    fo.close();

    return 0;

}