#include<iostream>
#include<vector>
using namespace std;
bool book[100000];
int dis[1000000];
#define Max 503
#define INF 1000000009
typedef struct zhugan {							//定义图
	int n, m,s;
	int bian[Max][Max];								//邻接矩阵
};
void putin(zhugan& a)								//输入图
{
	cin >> a.n >> a.m>>a.s;
	for (int i = 1; i <= a.n; i++)				//初始化邻接矩阵
	{
		for (int j = 1; j <= a.n; j++)
			a.bian[i][j] = INF;
		book[i] = 0;
		dis[i] = INF;
	}

	for (int i = 1; i <= a.m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		a.bian[u][v] = w;
	}
}




void dijiesitela(zhugan& a) {
	book[a.s] = 1;
	for (int i = 1; i <= a.n; i++)
	{
		dis[i] = a.bian[a.s][i];
	}
	dis[a.s] = 0;
	int min1 = INF;
	int index = 1;
	for (int i = 2; i <= a.n; i++)
	{
		int min1 = INF;
		int index=1;
		for (int j = 1; j <= a.n; j++) {

			if (book[j] == 0 && min1 > dis[j]) {
				min1 = dis[j];
				index = j;
			}



		}

		book[index] = 1;
		for (int j = 1; j <= a.n; j++)
		{


			if (book[j] == 0 && dis[j] > dis[index] + a.bian[index][j]) dis[j] = dis[index] + a.bian[index][j];
		}









	}
}
void puout(zhugan& a) {

	for (int i = 1; i <= a.n; i++)
	{
		cout << dis[i] << " ";
	}
}
int main()
{
	
	zhugan a;
	
	putin(a);
	dijiesitela(a);
	puout(a);


}