#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define N 5002
#define oo 100000000
using namespace std;

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

int nrnoduri,m,nonnegativ=1;
int distanta[N],viz[N],nr[N];
queue <int> Q;
vector < pair<int,int> > Graf[N];

void citeste_fa()
{
    int x,y,k,i;
    pair <int,int> p;
    f>>nrnoduri>>m;
    for(i=1;i<=nrnoduri;i++){
        f>>x>>y>>k;
        p=make_pair(y,k);
        Graf[x].push_back(p);
}   }

void aplica_bellman_ford_fa(int qq)
{
    int i,auxq,nod,cost;
    for(i=1;i<=nrnoduri;i++)
        if(i!=qq) distanta[i]=oo;
    Q.push(qq),viz[qq]=1;
    while(!Q.empty()&&nonnegativ==1){
        auxq=Q.front(),Q.pop(),viz[auxq]=0;
        for(unsigned int j=0;j<Graf[auxq].size();j++){
            nod=Graf[auxq][j].first,cost=Graf[auxq][j].second;
            if(distanta[nod]>distanta[auxq]+cost){
                distanta[nod]=distanta[auxq]+cost;
                if(viz[nod]==0){
                    Q.push(nod),viz[nod]=1,nr[nod]++;
                    if(nr[nod]>nrnoduri) nonnegativ=0;
}   }   }   }   }

void afiseaza_fa()
{
    if(nonnegativ==0){
        cout<<"Ciclu negativ!\n";
        return;
    }
    for(int i=2;i<=nrnoduri;i++)
        cout<<distanta[i]<<' ';
}

int main()
{
    citeste_fa();
    aplica_bellman_ford_fa(1);
    afiseaza_fa();
    return 0;
}