#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
string fisier="bellmanford";
ifstream fin(fisier+".in");
ofstream fout(fisier+".out");

int n, m, nod_start;
const int NMAX=50005, INF=1E9;
vector <pair<int, int>>graf[NMAX];
queue <int> coada;
int frecv[NMAX]; bool viz[NMAX];
int dist[NMAX];

void citire()
{
    fin>>n>>m;
    int x, y, cost;
    for (int i=1; i<=m; ++i)
    {
        fin>>x>>y>>cost;
        graf[x].push_back(make_pair(y, cost));
    }

    fin.close();
}
/*
void citire_2()
{
    fin>>n>>nod_start;
    int x, y, cost;
    while(fin>>x>>y>>cost)
        graf[x].push_back(make_pair(y, cost));
}
*/
void initializare()
{
    for (int i=1; i<=n; ++i)
    {
        frecv[i]=viz[i]=0;
        dist[i]=INF;
    }
}
bool ok=1;
void bellman_ford(int start)
{
    initializare();
    dist[start]=0, coada.push(start), viz[start]=1;
    while (!coada.empty())
    {
        int nod_curent=coada.front();
        ++frecv[nod_curent];
        if (frecv[nod_curent]>=n)
        {
                ok=0;
                return;//evitam un ciclu negativ
        }
        coada.pop();
        viz[nod_curent]=0;
        for (int i=0; i<graf[nod_curent].size(); ++i)
        {
            int vecin=graf[nod_curent][i].first;
            int cost=graf[nod_curent][i].second;
            if (dist[vecin]>dist[nod_curent]+cost)
            {
                dist[vecin]=dist[nod_curent]+cost;
                if (!viz[vecin])
                    coada.push(vecin);
            }
        }
    }
}
void afisare()
{
    if(!ok)
    {
        fout<<"Ciclu negativ!\n";
        return;
    }
    for (int i=1; i<=n; ++i)
        fout<<dist[i]<<' ';
    fout<<'\n';

    fout.close();
}
int main()
{
    citire();
    nod_start=1;
    bellman_ford(nod_start);
    afisare();
    return 0;
}