#include<bits/stdc++.h>
using namespace std;
struct Side{
	int w,nxt,to;
}sds[200001];
int sdh[200001];
long long pl[100001];
bool f[100001]; 
struct Point{
	int l,si;
	bool operator<(const Point &x) const{
		return l<x.l;
	} 
};
priority_queue<Point> que;
int main(){
	int n,m,s;
	cin>>n>>m>>s;
	int frm,to,w;
	for(int i=1;i<=m;i++){
		cin>>frm>>to>>w;
		sds[i].to=to;
		sds[i].w=w;
		sds[i].nxt=sdh[frm];
		sdh[frm]=i;
	}
	Point p;
	p.l=0,p.si=s;
	que.push(p);
	int INF=(1<<31)-1;
	for(int i=1;i<=n;i++) pl[i]=INF;
	pl[s]=0;
	while(que.size()){
		p=que.top();
		que.pop();
		int x=p.si;
		if(f[x]) continue;
		f[x]=true;
		for(int j=sdh[x];j!=0;j=sds[j].nxt){
			int y=sds[j].to;
			if(pl[y]>pl[x]+sds[j].w){
				pl[y]=pl[x]+sds[j].w;
				p.si=y;
				p.l=pl[y];
				que.push(p);
			}
		}
	}
	for(int i=1;i<=n;i++) cout<<pl[i]<<" ";
	return 0;
}

只对了第五个点