#include<iostream>
#include<fstream>
#define inf 1000000000
using namespace std;
int i,d[50001],k,ok,n,m,l[3][250001];
ofstream fout("bellmanford.out");
ifstream fin("bellmanford.in");
void citire_lm()
{
fin>>n>>m;
for(i=1;i<=m;++i)
    fin>>l[0][i]>>l[1][i]>>l[2][i];
}
int main()
{
citire_lm();
for(i=1;i<=n;++i) d[i]=inf;
d[1]=0;
k=0;
do
{
ok=1;
for(i=1;i<=m;++i)
    if(d[l[0][i]]+l[2][i]<d[l[1][i]])
    {
        d[l[1][i]]=d[l[0][i]]+l[2][i];
        ok=0;
    }
k++;
}while(ok==0&&k<=n+1);
if(k==n+1)
    fout<<"Ciclu negativ!"<<endl;
else
    for(i=2;i<=n;++i)
        fout<<d[i]<<' ';
fout.close();
return 0;
}