#include <fstream>
#include <queue>
#include <vector>
#define inf 2000000001
#define nmax 50001

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int m,n,dmin[nmax],nr[nmax];
queue <int> C;
struct muchie {int nod,val;};
muchie p;
vector <muchie> v[nmax];

void Citire()
{int i,x;
fin>>n>>m;
for(i=1;i<=m;i++)
   {fin>>x>>p.nod>>p.val;
    v[x].push_back(p);
   }
}

void bellmanford()
{bool neg=0;
int x,i;
for(i=2;i<=n;i++) dmin[i]=inf;
dmin[1]=0; C.push(1);
while(!C.empty()&&!neg)
   {x=C.front(); C.pop();
    nr[x]++;
    if(nr[x]==n) {neg=1;break;}
    for(i=0;i<v[x].size();i++)
        if(dmin[v[x][i].nod]>dmin[x]+v[x][i].val)
           {dmin[v[x][i].nod]=dmin[x]+v[x][i].val;
            C.push(v[x][i].nod);
           }
   }
if(neg==1) fout<<"Ciclu negativ!";
else for(i=2;i<=n;i++) if(dmin[i]==inf) fout<<"0 ";
                       else fout<<dmin[i]<<" ";
}

int main()
{
Citire();
bellmanford();

    return 0;
}