//bellman-ceva cu cicluri
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
constexpr int NX = 50010;
constexpr int inf = 9999999;
vector <pair <int, int>> G[NX];
//pair <int, int> p
//p.first --> nod de obicei
//p.second --> cost de obicei
//noi suntem smecheri si facem sort invers ca sort se face dupa first

queue <int> Q;
int viz[NX], distanta[NX];
int n, m, ok;

void bfs()
{
//trb sa fac distanta de la sursa la ea 0 si restul infinit in vectorul distanta
//iau mereu nodul 1 ca fiind inceputul
    for(int i=1; i<=n; ++i)
    distanta[i]=inf;
    Q.push(1);
    distanta[1]=0;
    while(!Q.empty())
    {
        int nod=Q.front();
        Q.pop();
        //vizitez nodul
        viz[nod]++;
        //daca am trecut de n ori inseamna ca e o muchie cu const negativ
        if(viz[nod]==n)
        {
            ok=1;
            return;
        }
        for(int i=0; i<G[nod].size(); i++)
        {
            if(distanta[G[nod][i].second]>distanta[nod]+G[nod][i].first)
            {
                distanta[G[nod][i].second]=distanta[nod]+G[nod][i].first;
                Q.push(G[nod][i].second);
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int x, y, z;
        fin>>x>>y>>z;
        G[x].push_back(make_pair(z, y));
    }
    bfs();
    if(ok==1)
    fout<<"Ciclu negativ!";
    else
    for(int i=2; i<=n; ++i)
    fout<<distanta[i]<<" ";
    return 0;

}