rt

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll inf=1e12;
ll m,n,s,a,b,c,x;
ll dis[5000005],vis[5000005];
ll head[5000005],nxt[5000005],to[5000005],w[5000005],cnt;
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q; 
void edge(ll u,ll v,ll mon){
	nxt[++cnt]=head[u];head[u]=cnt;
	to[cnt]=v;w[cnt]=mon;
}
int main(){
	scanf("%lld%lld%lld",&n,&m,&s);
	for(int i=1;i<=n;i++)dis[i]=inf;
	for(int i=1;i<=m;i++)scanf("%lld%lld%lld",&a,&b,&c),edge(a,b,c);
	dis[s]=0;q.push(make_pair(0,s));vis[s]=1;
	while(!q.empty()){
		x=q.top().second;q.pop();
		//cout<<"now is "<<x<<" queue len is "<<q.size()<<endl;
		for(int i=head[x];i;i=nxt[i]){
			dis[to[i]]=min(dis[to[i]],dis[x]+w[i]);
			if(!vis[to[i]])q.push(make_pair(dis[to[i]],to[i])),vis[to[i]]=1;
		}
	}
	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
	return 0;
}