#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
LL head[N], to[N], w[N], idx, ne[N];
LL dis[N], vis[N], num[N];
inline void add(int x, int y , int z)
{
	to[++idx] = y;
	w[idx] = z;
	ne[idx] = head[x];
	head[x] = idx;
}
LL n, m, s;
bool spfa(int k)
{
	memset(num , 0, sizeof(num));
	memset(vis , 0, sizeof(vis));
	memset(dis , 0x3f, sizeof(dis));
	stack<int> p;//先进后出
	//可能会有负环点进队列时，马上就出队列了
	//所以用栈
	p.push(k); 
	vis[k] = 1;
	dis[k] = 0;
	num[k]++;
	while(!p.empty())
	{
		int t = p.top();
		p.pop();
		vis[t] = 0;
		for(int i = head[t]; i ; i = ne[i])
		{
			if(dis[to[i]] > w[i] + dis[t])
			{
				dis[to[i]] = w[i] + dis[t];
				if(!vis[to[i]])
				{
					p.push(to[i]);
					num[to[i]]++;
					vis[to[i]] = 1;
					if(num[to[i]] >= n)
						return true;
				}
			}
		}
	}	
	return false;
}
int main()
{
	scanf("%lld%lld%lld", &n, &m, &s);
	for(LL i = 0, x, z, y; i < m; i++)
	{
		scanf("%lld%lld%lld", &x, &y, &z);
		add(x, y, z);
	}
	//超级原点 
	int k = n + 1;
	for(int i = 1; i <= n; i++)
		add(k, i, 0);
	//如果1 2 3联通，而4 5是负环，先判断有无负环 
	if(spfa(k))
	{ 
		//有，输出-1
		cout << "-1" << endl;
	}
	//没有，进行运算 
	else 
	{
		spfa(s);
		for(int i = 1; i <= n; i++)
		{
			if(dis[i] >= INF)
			{ 
				puts("NoPath");
				//不联通 
			}
			else
			{
				printf("%lld\n",dis[i]);
				//输出值 
			}
		}
	}
	return 0;
}

/*****************************************
备注：
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
LL head[N] , to[N] , w[N] , idx,ne[N];
LL dis[N] , vis[N], num[N] ,st[N] ,top = 0;
inline void add(int x, int y , int z)
{
	to[++idx] = y;
	w[idx] = z;
	ne[idx] = head[x];
	head[x] = idx;
}
LL n , m , s;
bool spfa(int k)
{
	memset(num , 0 ,sizeof(num));
	memset(vis , 0 ,sizeof(vis));
	memset(dis , 0x3f ,sizeof(dis));
	st[++top] = k;
	vis[k] = 1;
	dis[k] = 0;
	num[k]++;
	while(top > 0)
	{
		int t = st[top--];
		vis[t] = 0;
		for(int i = head[t] ; i ; i = ne[i])
		{
			if(dis[to[i]] > w[i] + dis[t])
			{
				dis[to[i]] = w[i] + dis[t];
				if(!vis[to[i]])
				{
					st[++top] = to[i];
					num[to[i]]++;
					vis[to[i]] = 1;
					if(num[to[i]] >= n)
						return true;
				}
			}
		}
	}	
	return false;
}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&s);
	for(LL i =0,x,z,y  ; i < m ; i++)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,z);
	}
	int k = n+1;
	for(int i = 1; i <= n ; i++)
		add(k , i , 0);
	if(spfa(k))
		cout << -1;
	else 
	{
		spfa(s);
		for(int i = 1 ;  i <= n ; i++)
		{

			if(dis[i] >= INF)
				puts("NoPath");
			else 
				printf("%lld\n",dis[i]);
		}
	}

	return 0;
}