#include<iostream>
#include<cstring>
#include<vector> 
#include <algorithm>
#include<queue>
using namespace std;
int n, m, s;
struct edge
{
	int v;//终点 
	int w;//边权 
};
vector<edge> e[100005];//u所有出边和边权 
priority_queue<edge> Q;//优先队列 
int d[100005];//存u到源点s的最小距离
int vis[100005];//标记u是否出圈，即是否走过 
int pre[100005];//记录前驱点 
int c;//记录前驱点个数 
int inf = 2 ^ 31 - 1;
void dj(int s)
{
	for (int i = 0; i <= n; i++)
	{
		d[i] = inf;
	}
	d[s] = 0;
	Q.push({ 0,s });
	while (!Q.empty())
	{
		edge t = Q.top();
		Q.pop();
		int u = t.w;
		if (vis[u])
		{
			continue;
		}
		vis[u] = 1;
		for (vector<edge>::iterator it = e[u].begin(); it != e[u].end(); it++)
		{
			edge ed = *it;
			int v = ed.v, w = ed.w;
			if (d[v] > d[u] + w)
			{
				d[v] = d[u] + w;
				pre[v] = u;
				Q.push({ -d[v],v });
			}
		}
	}
}
int dfs_cnt(int u)
{
	if (u == s)
	{
		c++;
		return c;
	}
	else
	{
		dfs_cnt(pre[u]);
		c++;
	}
}
int main()
{
	cin >> n >> m >> s;
	while (m--)
	{
		int u, v, w;
		cin >> u >> v >> w;
		e[u].push_back({ v,w });
	}
	dj(s);
	c = 0;
	cout << dfs_cnt(1);
	for (int i = 2; i <= n; i++)
	{
		c = 0;
		cout << " " << dfs_cnt(i);
	}


}