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

struct muchie{int a,c;}x ;

vector<muchie>v[50010];
queue<int>q;
bool viz[50010];

int n,m,i,j,a;
long long int c[50010];

void bellman_ford(){
int i = 0,x ;
long long int cnt= 0 ;
memset(c,0x3f3f3f3f,sizeof(c));
c[1] = 0;
q.push(1);
viz[1] = true;

while((!q.empty())&& (cnt <= (long long)(n)*((long long)(m))) + 2000){
	x = q.front();
	viz[x] = false;
	for(i  = 0 ; i < v[x].size();i++)
		if(c[v[x][i].a] > c[x] + v[x][i].c){
			c[v[x][i].a] = c[x] + v[x][i].c;
			if(!viz[v[x][i].a]){
				viz[v[x][i].a] = true;
				q.push(v[x][i].a);
				}
		}
	
	q.pop();
	cnt++;
	}

}

void print(){
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
int a,b,z,i;

scanf("%d %d",&n,&m);

for(i = 1; i <= m ;i++)
	{scanf("%d %d %d",&a,&b,&z);
	if(c[a] + z < c[b])
		{printf("Ciclu negativ!");
		return;
		}
	}
	for(i = 2; i <= n ; i++)
		printf("%lld ",c[i]);
}

int main(){
freopen("bellmanford.in","r",stdin);
scanf("%d %d",&n,&m);

for( i = 1; i <= m ; i++)
	{scanf("%d %d %d",&a,&x.a,&x.c);
	v[a].push_back(x);
	}
	
bellman_ford();

print();
	
return 0;}