#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define inf 10000000

using namespace std;

int x,y,n,m,dist[50002],cost[50002],pred[50002];
bool ok;
 ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");

vector< pair <int , int> >v;

void BFord()
{
    dist[1]=0;
    for(int i=2; i<=n; i++)dist[i]=inf,pred[i]=0;

    for(int i=1; i<=n; i++)
        for(int j=0; j<v.size(); j++)
        if(dist[v[j].first]+cost[j]<dist[v[j].second])
        {
            dist[v[j].second]=dist[v[j].first]+cost[j];
            pred[v[j].second]=v[j].first;
        }
    for(int i=0; i<v.size(); i++)
    if(dist[v[i].first]+cost[i]<dist[v[i].second]){g<<"Ciclu Negativ";ok=true;break;}

}

int main()
{

    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>cost[i-1];
        v.push_back(make_pair(x,y));
    }
    BFord();
    if(ok==false)for(int i=2; i<=n; i++)g<<dist[i]<<" ";

    return 0;
}