#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e4 + 5;
int dist[NMAX], n, m;
vector < pair <int, int> > g[NMAX];

void init()
{
    int i;
    for(i = 0;  i < NMAX; ++i)
        dist[i] = INT_MAX;
}

void citire()
{
    fin >> n >> m;

    int a, b, c;
    int i;

    for(i = 1; i <= m; ++i)
    {
        fin >> a >> b >> c;
        g[a].push_back({b, c});
    }
}

bitset <NMAX> inQueue;
queue < int > coada;
int reps[NMAX];
bool ciclu = false;

void solve()
{
    coada.push(1);
    dist[1] = 0;
    inQueue[1] = 1;
    int top;

    while(coada.empty() == false)
    {
        top = coada.front();
        coada.pop();
        inQueue[top] = 0;

        ++reps[top];
        if(reps[top] >= n)
        {
            ciclu = true;
            return ;
        }


        for(auto &it: g[top])
        {
            if(dist[top] + it.second < dist[it.first])
            {
                dist[it.first] = dist[top] + it.second;

                if(inQueue[it.first] == 0)
                {
                    coada.push(it.first);
                    inQueue[it.first] = 1;
                }
            }
        }
    }
}

void afis()
{
    if(ciclu)
        fout << "Ciclu negativ!";
    else for(int i = 2; i <= n; ++i)
            fout << dist[i] << ' ';
}

int main()
{
    init();
    citire();
    solve();
    afis();
    return 0;
}