#include <fstream>
#include <climits>
#include <queue>
#include <vector>
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int MAXN = 50010, INF = INT_MAX;

struct muchie
{
    int nod, cost;
    muchie (int a, int b) : nod(a), cost(b) {}
};

int N, M, viz[MAXN], cost[MAXN];
vector <muchie> G[MAXN];
queue <int> q;
bool sol = true;

void citire ()
{
    int x, y, c;

    fin >> N >> M;
    for (int i = 0; i < M; ++i)
    {
        fin >> x >> y >> c;
        G[x].push_back(muchie(y, c));
    }

    for (int i = 2; i <= N; ++i)
        cost[i] = INF;

    q.push(1);
}

void bfd ()
{
    while ( !q.empty() )
    {
        int x = q.front();
        int L = G[x].size();
        q.pop();
        for (int i = 0; i < L; ++i)
        {
            int y = G[x][i].nod;
            int val = G[x][i].cost;
            if (cost[x] + val < cost[y])
            {
                ++viz[y];
                if (viz[y] > N)
                {
                    sol = false;
                    return;
                }
                cost[y] = cost[x] + val;
                q.push(y);
            }
        }
    }
}

void afisare ()
{
    if ( sol )
    {
        for (int i = 2; i <= N; ++i)
        {
            if (cost[i] == INF)
                fout << "0 ";
            else
                fout << cost[i]
                 << " ";
        }
    }
    else
        fout << "Ciclu negativ!";
}

int main ()
{
    citire();
    bfd();
    afisare();

    fin.close();
    fout.close();

    return 0;
}