#include<cstdio>
#include<vector>
#include<queue>
#define f first
#define s second
using namespace std;
const int maxn = 50005;
const int INF = 1000000000;

int i , j , x , y , z , d[maxn] , n , m , cnt[maxn];
bool in[maxn];
vector < pair <int , int > > G[maxn];

void BF ()
{
	int i , j;
	queue <int> Q;
	
	for( i = 2 ; i <= n ; ++i ) 
		d[i] = INF;
	cnt[1] = 1;
	in[1] = 1;
	
	for( Q.push(1) ; ! Q.empty() ; ) {
		int act = Q.front();
		Q.pop(); in[act] = false;
		for( i = 0 ; i < G[act].size() ; ++i )
			if ( d[act] + G[act][i].s < d[G[act][i].f] ) {
				d[G[act][i].f] = d[act] + G[act][i].s;
				if ( !in[G[act][i].f] )  {
					Q.push(G[act][i].f);
					cnt[G[act][i].f]++;
					in[G[act][i].f] = 1;
					if ( cnt[G[act][i].f] > n ) {
						printf("Ciclu negativ!\n");
						return;
					}
			}
		}
	}
	
	for( i = 2 ; i <= n ; ++i ) 
		printf("%d ",d[i]);
}

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	for( i = 1 ; i <= m  ; ++i ) {
		scanf("%d %d %d",&x,&y,&z);
		G[x].push_back(make_pair(y,z));
	}
	
	BF();
	
return 0;
}