#include <stdio.h>
#include <vector>
#include <set>
using namespace std;

//class edge{
//	public: int from,to,cost;
//	public:edge(){}
//	public:edge(int f,int t,int c):from(f),to(t),cost(c){}
//s};

int n,m;
//edge edges[250000];
int dist[50000];
const int INF=50000005;
vector< vector<pair<int,int> > > G(50005);



int main(){
	int x,y,c;
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&x,&y,&c);
		G[x].push_back(pair<int,int>(y,c));
		//edges[i].from=x;edges[i].to=y;edges[i].cost=c;
	}
	
	for(int i=2;i<=n;i++)
		dist[i]=INF;
	dist[0]=0;
	//for(int i=1;i<=(n-1);i++){
	//	for(int j=0;j<m;j++){
	//		if(dist[edges[j].to]>dist[edges[j].from]+edges[j].cost)
	//			dist[edges[j].to]=dist[edges[j].from]+edges[j].cost;
	//	}
	//}
	
	set<int> current;
	set<int> next;
	current.insert(1);
	for(int i=1;i<=(n-1);i++){
		
		for(set<int>::iterator j=current.begin();j!=current.end();j++)
			for(int k=0;k<G[(*j)].size();k++){
				if(dist[(*j)]+G[(*j)][k].second<dist[G[(*j)][k].first])
				{	dist[G[(*j)][k].first]=dist[(*j)]+G[(*j)][k].second;
					next.insert(G[(*j)][k].first);
				}
			}
		//current.clear();
		current.clear();
		current=next;
		next.clear();	
	}
	bool ok=true;
	for(set<int>::iterator j=current.begin();j!=current.end();j++)
		for(int k=0;k<G[(*j)].size();k++){
			if(dist[(*j)]+G[(*j)][k].second<dist[G[(*j)][k].first])
			{ok=false;break;}
		}
	//for(int j=0;j<m;j++){
	//		if(dist[edges[j].to]>dist[edges[j].from]+edges[j].cost)
	//			{ok=false;break;}
	//	}
	if(!ok)
		printf("Ciclu negativ!");
	else
		for(int i=2;i<=n;i++)
			printf("%d ",dist[i]);	
			
	return 0;
}