#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

#define Nmax 50001

#define INF 0x3f3f3f3f

int N, M, D[Nmax], cnt[Nmax];
vector < pair <int,int> > G[Nmax];
bool viz[Nmax];
queue<int> Q;

int main() {
    freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	
	int i, j, k, nod, cost, fiu;
   
    scanf("%d %d",&N,&M);
	while(M--) {
          scanf("%d %d %d",&i,&j,&k);
          G[i].push_back(make_pair(j,k));
    }
    
	for(i=2; i<=N; i++) 
		D[i]=INF, viz[i]=false;
	
	Q.push(1), D[1]=0, viz[1]=true;
	
	while(!Q.empty()) {
		nod=Q.front();
		vector < pair <int,int> > :: iterator it;
		for(it=G[nod].begin(); it!=G[nod].end(); ++it) {
			fiu=it->first;
			cost=it->second;
			if(D[fiu]>D[nod]+cost) {
				D[fiu]=D[nod]+cost;
				if(!viz[fiu]) {
					cnt[fiu]++;
					if(cnt[fiu]>N) {
						printf("Ciclu negativ!\n");
						return 0;
					}
					Q.push(fiu);
					viz[fiu]=true;
				}
			}
		}
		viz[nod]=false;
		Q.pop();
	}
    
    for(i=2; i<=N; ++i) 
		printf("%d ",D[i]);
	printf("\n");
    
	return 0;
}