#include<fstream.h>
#define max 50000
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,m,d[max],c[max][max];
struct nod{int x,y;
	   };
 nod g[max];


void bellman()
{int i,j;
 for(i=1;i<n;i++)
 for(j=1;j<=m;j++)
 if(d[g[j].y]>d[g[j].x]+c[g[j].x][g[j].y])
 d[g[j].y]=d[g[j].x]+c[g[j].x][g[j].y];
}

void init()
{int i,j;
 fin>>n>>m;
 for(i=1;i<=m;i++)
 fin>>g[i].x>>g[i].y>>c[g[i].x][g[i].y];

 for(i=1;i<=n;i++)
 d[i]=max;
 }

int main()
{int i;
 init();
 d[1]=0;
 bellman();
 for(i=1;i<=m;i++)
 if(d[g[i].x]+c[g[i].x][g[i].y]<d[g[i].y])
 fout<<"gr contine cicluri de cost negativ";
 fout<<"\n";

 for(i=1;i<=n;i++)
 if(d[i]<max && d[i]) fout<<d[i]<<" ";
 fout<<"\n";

 fin.close();
 fout.close();
 return 0;
 }