#include<fstream>
#include<queue>
#include<vector>
#define inf 2000000
#define dim 50002
using namespace std;
ifstream  f("bellmanford.in");
ofstream  g("bellmanford.out");
int D[dim],n,m,x,y,c,i,viz[dim],contor[dim];
vector<int>G[dim],C[dim];
queue<int>Q;
void bellman (){
	for(i=2;i<=n;i++)
		D[i]=inf;
	D[1]=0;
	Q.push(1);
	while(!Q.empty()){
		x=Q.front();
		Q.pop();
		viz[x]=0;
		for(int i=0;i<G[x].size();++i){
			
			if(D[G[x][i]]>D[x]+C[x][i]){
				D[G[x][i]]=D[x]+C[x][i];
				if(!viz[G[x][i]]){
					if(contor[G[x][i]]>n){
						g<<"Ciclu negativ!";
						return ;
					}
					else{
					viz[G[x][i]]=1;
					++contor[G[x][i]];
					Q.push(G[x][i]);
					}
				}
			}
		}
	}
	for(i=2;i<=n;i++)
		g<<D[i]<<" ";
}
int main (){
	f>>n>>m;
	for(i=1;i<=m;i++){
		f>>x>>y>>c;
		G[x].push_back(y);
		C[x].push_back(c);
	}
	bellman();
	return 0;
}