/*
Algoritmul Bellman-Ford
Se dă un graf orientat conex cu N noduri şi M muchii cu costuri. Definim un lanţ ca fiind un şir de noduri cu proprietatea că între oricare două consecutive există o muchie. Costul unui lanţ este dat de suma costurilor muchiilor care unesc nodurile ce îl formează. Definim un ciclu ca fiind un lanţ cu proprietatea că primul element al său este egal cu ultimul.

Cerinţă
Să se determine dacă în graful dat există un ciclu de cost negativ. Dacă nu există, să se determine costul minim al unui lanţ de la nodul 1 la fiecare dintre nodurile 2, 3, ... , N-1, N.

Date de intrare
Fişierul de intrare bellmanford.in conţine pe prima linie numerele N şi M cu semnificaţia din enunţ. Pe următoarele M linii se vor afla câte 3 numere x, y şi c cu semnificaţia că există o muchie de cost c de la nodul x la nodul y.

Date de ieşire
În fişierul de ieşire bellmanford.out se va afişa pe prima linie mesajul "Ciclu negativ!" dacă în graf există un astfel de ciclu sau, în caz contrar, N-1 numere separate printr-un spaţiu. Al i-lea număr va reprezenta costul minim al unui lanţ de la nodul 1 la nodul i+1.

Restricţii
1 ≤ N ≤ 50 000.
1 ≤ M ≤ 250 000.
Costurile muchiilor sunt numere întregi cel mult egale în modul cu 1 000.
*/
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define NMAX 50005

using namespace std;

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

vector < pair < int, int > > v[NMAX], v2[NMAX];
queue < int > q;
map < pair < int, int >, int > M;
int n, viz[NMAX];
bool okk;

bool gasit_ciclu();
void dfs(int x);

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0),cout.tie(0);
    int m, x, y, z, i, nr, r[NMAX];
    bool ok, fr[NMAX];

    fin >> n >> m;
    while(m--)
    {
        fin >> x >> y >> z;
        v[x].pb({y, z});
    }

    for(i = 2; i <= n; i++) fr[i] = 0, r[i] = INT_MAX;
    ok = 1, nr = 0, r[1] = 0, fr[1] = 1, q.push(1);
    while(q.empty() == 0)
    {
        x = q.front(), q.pop();

        fr[x] = 0;
        nr++;
        if(nr == n)
        {
            nr = 0;
            if(gasit_ciclu() == 1)
            {
                ok = 0;
                break;
            }
        }

        for(auto it:v[x])
            if(r[x] + it.second < r[it.first])
            {
                r[it.first] = r[x] + it.second;
                if(M[{x,it.first}] == 0) M[{x,it.first}] = 1, v2[x].pb(it);
                if(fr[it.first] == 0) fr[it.first] = 1, q.push(it.first);
            }
    }

    if(ok == 1) for(i = 2; i <= n; i++) fout << r[i] << ' ';
    else fout << "Ciclu negativ!";


    return 0;
}

bool gasit_ciclu()
{
    int i;

    for(i = 1; i <= n; i++) viz[i] = 0;
    okk = 0;
    dfs(1);
    return okk;
}

void dfs(int x)
{
    if(okk == 0)
    {
        viz[x] = 1;
        for(auto it:v2[x])
        {
            if(okk == 1) break;
            else if(viz[it.first] == 0) dfs(it.first);
            else if(viz[it.first] == 1)
            {
                okk = 1;
                break;
            }
        }

        viz[x] = 0;
    }
}
/*
IN:
5 8
1 3 -3
1 5 7
3 2 -2
3 4 7
5 1 4
5 2 3
5 3 4
4 5 3

OUT:
-5 -3 4 7
*/

//https://infoarena.ro/job_detail/2796392