#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <deque>
#include <list>
#include <ctime>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream ff("bellmanford.in");
ofstream gg("bellmanford.out");

#define max 50001
#define inf 0xffffff
struct per{ int b,c; per(int b0=0,int c0=0){b=b0; c=c0;}};
vector<per> vv[max];
queue<int> qq[2];
bool ww[max];
int n, m, dd[max];

void bel(){
	int x0=0, x1=1, x, y, c, l;
	for(int i=1;i<=n;i++) dd[i]=inf;
	dd[1]=0;
	qq[x0].push(1);
	for(int k=1;k<n;k++){
		memset(ww, 0, sizeof(ww));
		while(qq[x0].size()>0){
			x=qq[x0].front(); qq[x0].pop();
			l=vv[x].size();
			for(int i=0;i<l;i++){
				y=vv[x][i].b;
				c=vv[x][i].c;
				if(dd[y]>dd[x]+c){
					dd[y]=dd[x]+c;
					if(!ww[y]){qq[x1].push(y);ww[y]=1;}
				}
			}
		}
		x0^=1; x1^=1;
	}
	if((int)qq[0].size()>0) gg << "Ciclu negativ!\n"; else
	for(int i=2;i<=n;i++) gg << dd[i] << " ";
}

int main(){
	int a, b, c;
	ff >> n >> m;
	for(int i=0;i<m;i++){
		ff >> a >> b >> c;
		vv[a].push_back(per(b,c));
	}
	bel();
	return 0;
}