RT

#include <bits/stdc++.h>
using namespace std;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
int dis[30001],vis[30001],a,f[1000001],b,total,c,d,i,n,j,k;
int to[10001],val[10001],nex[10001];
struct w{
	int to,val,nex;
}g[100001];
void add(int x,int y,int z){
	g[++total].to=y;
	g[total].val=z;
	g[total].nex=f[x];
	f[x]=total;
}
int main(){
	int p;
    cin>>a>>n>>p;
    for(i=1;i<=n;++i){
    	cin>>b>>c>>d;
    	add(b,c,d);
	}
	memset(dis,1<<31-1,sizeof(dis));
	dis[p]=0;
	q.push(make_pair(0,p));
	while(q.size()){
		k=q.top().second,q.pop();
		if(vis[k])continue;
		vis[k]=1;
		for(i=f[k];i;i=g[i].nex){
			if(dis[g[i].to]>dis[k]+g[i].val)
			dis[g[i].to]=dis[k]+g[i].val,
			q.push(make_pair(dis[g[i].to],g[i].to));
			}
		}
	for(i=1;i<=a;++i)
	cout<<dis[i]<<" ";
	return 0;
}