#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;

typedef pair<int,int> PII;
const int N = 10e6;
int h[N],ne[N],w[N],e[N],idx;
int st[N],d[N];
int n,m,s;
priority_queue<PII , vector<PII> ,greater<PII> > heap;

void add(int a, int b, int c)
{
	e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
}
void dijkstra()
{
	memset	( d,0x3f,sizeof d);
	d[s] = 0;
	
	heap.push({s,0});
	
	while( !heap.empty())
	{
		auto t = heap.top();
		heap.pop();
		int v = t.first;int dis = t.second;
		
		if(st[v]) continue;
		st[v] = 1;
		for( int i = h[v] ; i != -1 ; i = ne[i])
		{
			int j = e[i];
			if( d[j] > dis + w[i])
			{
				d[j] = dis + w[i];
				heap.push({j,d[j]});
			}
		}
	}
}
int main()
{
	cin >> n >> m >> s;
	memset( h, -1 ,sizeof h);
	
	while( m--)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
	dijkstra();
	for( int i = 1; i <= n; i++) cout << d[i] << ' ';
}