#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
const int N=50001;
const int INF=1<<30;
struct NOD {int y,cost;};
int n,m,x,i,d[N], nrq[N];
bool inq[N];
vector<NOD>a[N];
queue<int>q;
int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y,cost;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&x,&y,&cost);
		a[x].push_back((NOD){y,cost});
	}
	for(int i=1;i<=N;++i)
		d[i]=INF;
	q.push(1);
	d[1]=0;
	while(!q.empty()){
		x=q.front();
		q.pop();
		inq[x]=false;
		for(size_t i=0; i<a[x].size();++i){
			y=a[x][i].y;
			if(d[x]+a[x][i].cost<d[y]){
				d[y]=d[x]+a[x][i].cost;
				if(!inq[y]){
					q.push(y);
					inq[y]=true;
					nrq[y]++;
					if(nrq[y]==n){
						printf("Ciclu negativ!\n");
						return 0;
					}
				}
			}
		}
	}
	for(int i=2;i<=n;++i)
		printf("%d ",d[i]);
	return 0;
}