#include<bits/stdc++.h>
using namespace std;
int n,m,s,cnt,he[10005],d[10005],bz[10005];
struct node
{
	int first,second;
};
struct edge{
	int net;
	int to;
	int w;
}e[500005];
priority_queue<node> q;
void add(int a, int b, int c)
{
	e[++cnt].net=he[a];
	e[cnt].to=b;
	e[cnt].w=c;
	he[a]=cnt;
}
bool operator < (node x, node y)
{
	return x.second > y.second;
}
void dij(int s) {
	for(int i=1; i<=n; ++i) d[i]=INT_MAX/2;
	d[s]=0; 
	q.push({s,0});
	for(int i=1;i<=n;i++)
	{
		int x=q.top().first; q.pop();
		while(bz[x]) {
			x=q.top().first;
			q.pop();
		} 
		bz[x]=1;
		for(int j=he[x]; j; j=e[j].net)
		{
			if(d[e[j].to]>d[x]+e[j].w) {
				d[e[j].to]=d[x]+e[j].w;
				q.push({e[j].to,d[e[j].to]});
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>s;
	int x,y,z;
	for(int i=1;i<=m;i++) {
		cin>>x>>y>>z;
		add(x,y,z);
	}
	dij(s);
	for(int i=1;i<=n;i++) {
		cout<<d[i]<<' ';
	}
	return 0;
}