#include<bits/stdc++.h>
using namespace std;
long long n,m,s,dis[10005],vis[10005],h[10005],tot;
priority_queue<pair<int,int> > q;
struct node{
	int next;
	int to;
	int w;
}e[10005];
void add(int x,int y,int z){
	tot++;
	e[tot].w=z;
	e[tot].to=y;
	e[tot].next=h[x];
	h[x]=tot;
}
void d(){
	while(q.size()){
		int x=q.top().second;
		q.pop();
		if(vis[x]){
			continue;
		}
		vis[x]=1;
		for(int i=h[x];i;i=e[i].next){
			int y=e[i].to;
			int w=e[i].w;
			if(vis[y]==0&&dis[y]>dis[x]+w){
				dis[y]=dis[x]+w;
				q.push(make_pair(-dis[y],y));
			}
		}
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++){
		dis[i]=2147483647;
	}
	dis[1]=0;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	q.push(make_pair(0,s));
	d();
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}

大佬求助 QWQWQWQWQWQ