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

elem Q[DIM];
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;
int p,u,i;

p=u=1;
Q[u].nod=1;
Q[u].cost=0;
inQ[1]=1;

while(p<=u){

nc=Q[p++];
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[++u]=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;}