using System;
using System.Collections;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using System.Threading.Tasks;

/*
・概要
Bellman-Ford法は、
重み付き有向グラフにおける単一始点の最短経路問題を解くアルゴリズム。
辺の重みに負数が存在する場合に主に使う。
（cf. 辺の重みが非負数ならば、ダイクストラ法の方が高速）

・使用法
	1. BellmanFordクラスのインスタンスを作成
	引数は、頂点数N、始点の番号source
	（e.g. BellmanFord graph = new BellmanFord(N,source);）

	2. 与えられた辺を追加
	引数は、始点、終点、重み
	（e.g. graph.AddEdge(start,goal,value);）

	3. BellmanFord法で最短距離を決定する
	（e.g. graph.SetDist();）

	4. 負の経路が存在するかを判定
	引数はそれぞれ、
	bool 始点から到達可能な地点にある閉路だけを対象とするか、
	int 始点から終点goalに達するまでの道に、閉路があるか
	（終点に達するまでかどうか気にしない場合は、-1を入力すること）
	（e.g. bool found = graph.NegativeCircle(true,N-1);）

	5. （最短経路が見つかった場合）始点からの最短距離を取得する
	引数は、目的地のインデックス
	（e.g. long ans = graph.GetDist(N-1);）
	→そもそも到達不可能な場合、long.MaxValueを返す

・アルゴリズム（計算量は O (V * E)：Vは頂点の数、Eは辺の数）
ループを回して、各ノードへの最短距離を更新し続ける。

・詳細

*/

class Program
{
	//Main
	static void Main(string[] args)
	{

		//出力準備（AutoFlushを切る）
		var sw = new StreamWriter(Console.OpenStandardOutput()){AutoFlush = false};
		Console.SetOut(sw);

		/*
		出力処理の開始
		*/
		Solve();

		/*
		出力処理の完了
		*/

		//出力終了
		Console.Out.Flush();
	}

	//Main
	static void Solve()
	{
		//読み込む
		string[] S = Console.ReadLine().Split(' ');
		int N = int.Parse(S[0]);
		int M = int.Parse(S[1]);
		int start = int.Parse(S[2]);

		//1. BellmanFordクラスのインスタンスを作成
		//引数は、頂点数N、始点の番号start
		BellmanFord graph = new BellmanFord(N,start);

		//2. 与えられた辺を追加
		for(int i=0; i<M; i++){
				string[] line = Console.ReadLine().Split(' ');
				int a = int.Parse(line[0]);
				int b = int.Parse(line[1]);
				long c = long.Parse(line[2]);

				//辺を追加
				/*
				引数は、始点、終点、重み
				*/
				graph.AddEdge(a,b,c);
		}

		//3. BellmanFord法で最短距離を決定する
		graph.SetDist();

		//4. スタート地点をから到達可能な負の閉路があるか判定
		bool found = graph.NegativeCircle(true, -1);

		//出力
		//見つからなかった場合
		if(!found){
			//各頂点について処理
			for(int i=0; i<N; i++){
				//5. 始点からの最短距離を取得する
				//引数は、目的地のインデックス
				long ans = graph.GetDist(i);

				//到達できない場合（INFが返される）
				if(ans == long.MaxValue){
					Console.WriteLine("INF");
				}
				//見つかった場合
				else{
					Console.WriteLine(ans);
				}
			}
		}
		//見つかった場合
		else{
			Console.WriteLine("NEGATIVE CYCLE");
		}
	}
}



//Bellman-Ford法を用いて、最短距離を求める為のクラス
class BellmanFord{
	//最短距離の初期化に使う変数
	/*
	大き過ぎると、オーバーフローして大小比較にバグが生じるので注意！！！！
	*/
	static readonly long inf = 10000000000000;

	//辺を保存する構造体
	public struct Edge
	{
		//始点
		public int Start;
		//終点
		public int Goal;
		//重み（負数もOK）
		public long Value;

		public Edge(int s, int g, long v){
			this.Start = s;
			this.Goal = g;
			this.Value = v;
		}
	}

	//辺を保存するリスト
	List<Edge> edgeList;
	//各頂点への最短距離を保存する配列
	long[] minDist;
	//始点から到着可能かを示すフラグ
	bool[] connected;
	//始点
	int source;
	//何らかの負の閉路が存在するか
	bool negativeCircle;
	//始点から到達可能な場所に、負の閉路が存在するか
	bool negativeCircleConnected;
	//始点を通じてある終点に向かうまでに、負の閉路が存在するか
	bool[] negativeCircleToGoal;

	//コンストラクタ
	/*
	引数は頂点数、始点の番号
	*/
	public BellmanFord(int vertex, int source){
		this.edgeList = new List<Edge>();
		this.source = source;

		//各頂点への最短距離をinfで初期化
		//但し、始点の場合には0とする
		this.minDist = new long[vertex];
		for(int i=0; i<vertex; i++){
			if(i == source){
				continue;
			}else{
				minDist[i] = inf;
			}
		}

		//始点から繋がっているかの配列を初期化
		this.connected = new bool[vertex];
		//始点はtrue
		this.connected[source] = true;

		//ある終点に向かうまでに、負の閉路が存在するか
		this.negativeCircleToGoal = new bool[vertex];
	}

	//辺を追加するメソッド
	/*
	引数は、始点、終点、重み
	*/
	public void AddEdge(int start, int goal, long value){
		Edge edge = new Edge(start, goal, value);
		//始点から繋がっていることを示す
		if(start == this.source || this.connected[start]){
			this.connected[goal] = true;
		}
		this.edgeList.Add(edge);
	}

	//Bellman-Ford法で、最短距離を求めるメソッド
	public void SetDist(){
		//頂点数と辺数
		int V = this.minDist.Length;
		int E = this.edgeList.Count();

		//ループで最小値を更新
		//各ノードへの到達最小値を更新し続ける
		for(int i=0; i<V; i++){
			for(int j=0; j<E; j++){
				//当該頂点の始点、終点、重み
				int start = edgeList[j].Start;
				int goal = edgeList[j].Goal;
				long value = edgeList[j].Value;

				//始点から繋がっていることを示す
				if(start == this.source || this.connected[start]){
					this.connected[goal] = true;
				}

				//最小値を更新できる場合（この辺を使った方が重みが少ない場合）
				if(this.minDist[goal] > this.minDist[start] + value){
					this.minDist[goal] = this.minDist[start] + value;

					//V-1回目で依然として更新が行われる場合
					if(i == V-1){
						//何らかの負の経路あり
						this.negativeCircle = true;

						//始点から到達可能な場合
						if(connected[start]){
							//始点から到達可能な負の閉路あり
							this.negativeCircleConnected = true;
						}

						//goalに到達する負の経路あり
						this.negativeCircleToGoal[goal] = true;
					}
				}
			}
		}
	}

	//負の閉路の存在を判定する関数
	/*
	引数はそれぞれ、
	bool 始点から到達可能な地点にある閉路だけを対象とするか、
	int 始点から終点goalに達するまでの道に、閉路があるか
	→終点に達するまでかどうか気にしない場合は、-1を入力すること
	*/
	public bool NegativeCircle(bool onlyConnected, int goal){
		//終点を限定しない場合
		if(goal < 0){
			//終点から到達可能な点に限定する場合
			if(onlyConnected){
				return this.negativeCircleConnected;
			}
			//どこかに閉路があれば良い場合
			else{
				return this.negativeCircle;
			}
		}
		//終点を限定する場合
		else{
			return this.negativeCircleToGoal[goal];
		}
	}

	//始点からの最短距離を出力
	public long GetDist(int goal){
		//始点から繋がっている場合、最短距離を返す
		if(this.connected[goal]){
			return this.minDist[goal];
		}
		//始点から到達不可能な場合、INFを返す
		else{
			return long.MaxValue;
		}
	}
}



Measured memory_bytes: 18240