#include<bits/stdc++.h>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
const int DIM=50001;
const int oo=1000001;
struct elem{int nod,cost;
};

queue<elem>Q;
vector<elem>L[DIM];

int n,m,d[DIM],inQ[DIM],itnod[DIM];

void citire(){
in>>n>>m;
elem w;
int i,x,y,c;
for(i=1;i<=m;i++)
{in>>x>>y>>c;
w.nod=y;w.cost=c;
L[x].push_back(w);

}}

int rez(){
for(int i=1;i<=n;i++)d[i]=oo;
d[1]=0;
elem nc,nv,w;
int i;


w.nod=1;
w.cost=0;
Q.push(w);
inQ[1]=1;

while(!Q.empty()){

nc=Q.front();
Q.pop();
inQ[nc.nod]=0;
for(i=0;i<L[nc.nod].size();i++)
{nv=L[nc.nod][i];
if(d[nv.nod]>d[nc.nod]+nv.cost){
  d[nv.nod]=d[nc.nod]+nv.cost  ;
  if(!inQ[nv.nod]){inQ[nv.nod]=1;Q.push(nv);}
  itnod[nv.nod]++;
  if(itnod[nv.nod]>n){out<<"Ciclu negativ!";out.close();return 0;}

}}
}
for(i=2;i<=n;i++)out<<d[i]<<" ";
out<<"\n";
out.close();
}




int main(){
citire();
rez();
return 0;}