#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;
   
    scanf("%d %d",&N,&M);
	while(M--) {
          scanf("%d %d %d",&i,&j,&k);
          G[i].push_back(make_pair(j,k));
    }
    
    for(i=1; i<=N; ++i) 
		viz[i]=false, D[i]=INF, cnt[i]=0;
    
	D[1]=0, viz[1]=true, cnt[1]=1, Q.push(1);
    
	while(!Q.empty()) {
        k=Q.front();
        vector < pair <int,int> > :: iterator it;
        for(it=G[k].begin(); it!=G[k].end(); ++it) {
			nod=it->first;
			cost=it->second;
            if(D[nod]>D[k]+cost) {
               D[nod]=D[k]+cost;
               if(!viz[nod]) {
				   Q.push(nod);
                   viz[nod]=true;
                   cnt[nod]++;
                   if(cnt[nod]==N) {
					   printf("Ciclu negativ!\n");
					   return 0;
				   }
			   }
			}
			viz[k]=false;
			Q.pop();
		}
	}
    
    for(i=2; i<=N; ++i) 
		printf("%d ",D[i]);
	printf("\n");
    
	return 0;
}