#include <bits/stdc++.h>

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

///declaram numarul maxim de varfuri si o valuare foarte mare
const int maxval=2000000;
const int maxnod=50001;
///cream o structura vecin in care tinem minte costul pana la predecesor si predecesorul;
struct vecin
{
    int j;
    int c;
};
vector <vecin>v[maxnod];
int d[maxnod];///reprezinta distanta minima de la nodul 1 la nodul i
int p[maxnod];///tine minte de cate ori sa folosit fiecare nod ---se foloseste pentru a vedea daca exista ciclu negativ
int t[maxnod];///reprezinta tata
///Numarul de noduri si numarul de muchii
int n,m;
///Coada in care vom insera primul nod, parcurgerea se face asemanator BF
queue <int> q;

void citire()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        vecin w;
        ///vecinul w tine minte pe predecesorul lui x(adica unde avem muchie) si pe
        int x;
        f>>x>>w.j>>w.c;
        v[x].push_back(w);
    }
}

void afis()
{
    for(int i=1; i<=n; i++)
        if(d[i]!=maxval&&d[i]!=0) g<<d[i]<<" ";
    g<<'\n';
}

int belmanford(int s)
{
    ///initializam distantele cu infinit
    for(int i=1; i<=n; i++)d[i]=maxval;
    ///distanta la nodul de start este 0
    d[s]=0;
    t[s]=0;///tata de start este 0
    ///punem in coada nodul de unde plecam
    q.push(s);
    int k;
    ///cat timp coada nu este vida repetam operatiile
    while(!q.empty())
    {
        k=q.front();///punem intr o variabila prima valoare din coada si apoi stergem prima val din coada
        q.pop();
        p[k]++;///am folosit nodul k din nou
        if(p[k]>=n) return 1;///ciclu negativ ===adica ar fii un ciclu in care s ar invartii la infinit algoritmul
        ///parcurgem toti vecinii lui nodului actual s
        for(int i=0; i<v[k].size(); i++)
        {
            /// verificam daca exista o muchie de cost minim mai mica
            if(d[v[k][i].j]>d[k]+v[k][i].c)
            {
                ///schimbam distanta cu cea mai mica
                d[v[k][i].j]=d[k]+v[k][i].c;
                ///adaugam in coada noul nod
                q.push(v[k][i].j);
                ///k e tata celui spre care am imbunatatit
                t[v[k][i].j]=k;
            }
        }
    }
    return 0;
}

int main()
{
    citire();
    ///s reprezinta nodul de unde plecam
    if(belmanford(1)==0)
    {
        afis();
    }
    else g<<"Ciclu negativ!";
}