#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll s,n,m,dis[100005],bj[100005],tot[100005];
vector<ll> son[100005];
vector<ll> sonw[100005];
priority_queue<pair<ll,ll> >q;
void dij(ll x) {
	memset(bj,0,sizeof(bj));
	for(ll i=1;i<=n;i++) dis[i]=LONG_LONG_MAX;
	dis[x]=0;
	q.push(make_pair(-dis[x],x));
	while(!q.empty()) {
		x=q.top().second;
		q.pop();
		if(bj[x]) continue;
		bj[x]=1;
		for(ll i=0;i<tot[x];i++) {
			ll y=son[x][i];
			if(bj[y]==0&&dis[y]>dis[x]+sonw[x][i]) {
				dis[y]=dis[x]+sonw[x][i];
				q.push(make_pair(-dis[y],y));
			}
		}
	}
}
int main() {
	cin>>n>>m>>s;
	for(ll i=1;i<=n;i++) {
		ll x,y,w;
		cin>>x>>y>>w;
		son[x].push_back(y);
		sonw[x].push_back(w);
		tot[x]++;
	}
	dij(s);
	for(ll i=1;i<=n;i++) cout<<dis[i]<<' ';
	return 0;
}