#include<fstream>
#include<vector>
#define N 50001
using namespace std;
ifstream F("bellmanford.in");
ofstream G("bellmanford.out");
vector<int> g[N],h[N];
int m,n,i,k,l,r,d[N],e[7*N],u[N],j,t;
bool v[N];
int main()
{
F>>n>>m;
while(m--)
F>>i>>j>>k,g[i].push_back(j),h[i].push_back(k);
for(i=1;i<=n;++i)
d[i]=N;
for(k=l=r=d[1]=0,e[r++]=v[1]=1;l<r&&!k;)
for(i=e[l++],t=g[i].size(),v[i]=j=0;(j<t&&!k);++j)
if(d[g[i][j]]>d[i]+h[i][j]) {
d[g[i][j]]=d[i]+h[i][j];
if(!v[g[i][j]]) {
if(u[g[i][j]]>n)
k=1;
else
e[r++]=g[i][j],v[g[i][j]]=1,++u[g[i][j]];
}
}
if(k)
G<<"Ciclu negativ!";
else
for(i=2;i<=n;++i)
G<<d[i]<<" ";
return 0;
}