#include <bits/stdc++.h>
#define inf 2e9
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector<pair<int,int> >v[50005];
queue<pair<int,int> >q;
int n,p,x,y,cost,d[50005],viz[50005];

void djk(int nod){
	for(int i=2;i<=n;i++){
		d[i]=inf;
	}
	q.push({0,nod});
	d[nod]=0;
	while(!q.empty()){
		nod=q.front().second;
		//cost=q.front().first;
		q.pop();
		viz[nod]++;
		//d[nod]=cost;
		if(viz[nod]>n){
			fout<<"Ciclu negativ!";
			n=-90;
            return;
		}
		for(auto it:v[nod]){
			if(d[it.second]>d[nod]+it.first){
				d[it.second]=d[nod]+it.first;
				q.push({it.first,it.second});
			}
		}
	}
}

int main() {

	fin>>n>>p;
	while(fin>>x){
		fin>>y>>cost;
		v[x].push_back({cost,y});
	}
	djk(1);
	if(n==-90)return 0;
	for(int i=2;i<=n;i++){
		fout<<d[i]<<' ';
	}
	return 0;

}