#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
using namespace std;
struct nod_{
    int nod;
    int lg;
};
#define oo 0x3f3f3f3f
#define foreach(v) for(typeof (v).begin() it=(v).begin();it!=(v).end();it++)
vector<nod_> G[50005];
queue<int> q;
int n,m,nr[50005],cost[50005],isin[50005];

inline void citire()
{int x,y,z,i;
ifstream fin("bellmanford.in");
fin>>n>>m;
for(i=1;i<=m;i++)
 {fin>>x>>y>>z;
 G[x].push_back((nod_){y,z});
 }
 fin.close();
}




int main()
{int i,p,u;
    citire();
q.push(1);
nr[1]=1;
cost[1]=0;
isin[1]=1;
for(i=2;i<=n;i++)
  cost[i]=oo;
p=1;
while(!q.empty()&&p)
{u=q.front();
q.pop();
isin[u]=0;
foreach(G[i])
{if(cost[u]+it->lg<cost[it->nod])
{
cost[it->nod]=cost[u]+it->lg;
if(!isin[u])
  {q.push(it->nod);
  nr[it->nod]++;

  isin[it->nod]=1;
  if(nr[it->nod]>n)
  p=0;
  }}}}
  ofstream fout("bellmanford.out");
if(p==0)
 cout<<"Ciclu negativ!";
 else
 for(i=2;i<=n;i++)

 fout<<cost[i]<<" ";
 fout.close();

return 0;
}