rt
wa #2 #9 #10

#include <cstdio>
#include <cstring>
#include <algorithm>

using std::min;

const int N = 100005;
const int M = 200005;

int n, m, s;
int u[M], v[M], w[M];
int dis[N];

void bf()
{
	memset(dis, 0x3f, sizeof dis);
	dis[s] = 0;
	
	for (int i = 1; i < n; i++)
	{
		bool si = 0;
		for (int j = 1; j <= m; j++)
		{
			if (dis[u[j]] + w[j] < dis[v[j]])
			{
				dis[v[j]] = dis[u[j]] + w[j];
				
				si = 1;	
			}
		}
		
		if (!si)
		{
			break;
		}
	}
}

int main()
{
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= m; i++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		u[i] = a;
		v[i] = b;
		w[i] = (!w[i] ? c : min(w[i], c));
	}
	
	bf();
	
	for (int i = 1; i <= n; i++)
	{
		printf("%d ", dis[i] != 0x3f3f3f3f ? dis[i] : 2147483647);
	}
	
	return 0;
}