#include <stdio.h>
#include <limits.h>
int main(){
	int n,m,s,i,j;
	scanf("%d%d%d",&n,&m,&s);
	int e[n][3],dist[n];
	for(i=0;i<m;i++){
		for(j=0;j<3;j++){
			scanf("%d",&e[i][j]);
		}
	}
	for(i=0;i<n;i++){
		dist[i]=INT_MAX;
	}
	dist[s]=0;
	for(i=0;i<n-1;i++){
		for(j=0;j<m;j++){
			if(dist[e[j][0]]!=INT_MAX&&dist[e[j][1]]>dist[e[j][0]]+e[j][2]){
				dist[e[j][1]]=dist[e[j][0]]+e[j][2];
			}
		}
	}
	for(j=0;j<m;j++){
		if(dist[e[j][0]]!=INT_MAX&&dist[e[j][1]]>dist[e[j][0]]+e[j][2]){
			printf("NEGATIVE CYCLE");
			return 0;
		}
	}
	for(i=0;i<n;i++){
		if(dist[i]==INT_MAX){
			printf("INF\n");
		}
		else{
			printf("%d\n",dist[i]);
		}
	}
	return 0;
}