图论萌新求调，0荤

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
struct node {
	long long u,v,w;
	bool operator > (const node& a) const {
		return w > a.w;
	}
};
int len=0;
priority_queue< node , vector < node > , greater < node > >q;
node a[200010];
bool vis[200010];
long long ans[200010];
void dig() {
	q.push({0,k,0});
	while(!q.empty()) {
		node uu=q.top();
		q.pop();
		if(vis[uu.u])continue;
		vis[uu.u]=1;
		for(int i=1; i<=m; i++) {
			if(vis[a[i].v])continue ;
				if(	ans[a[i].v]>ans[a[i].u]+a[i].w) {
					ans[a[i].v]=ans[a[i].u]+a[i].w;
						q.push(a[i]);
			}
		}
	}
}
int main() {
	cin>>n>>m>>k;
	for(int i=1; i<=m; i++) {
		int x,y,z;
		cin>>x>>y>>z;
		len++;
		a[len].u=x;
		a[len].v=y;
		a[len].w=z;
	}
	for(int i=1;i<=n;i++)
	ans[i]=INT_MAX;
	ans[k]=0;
	dig();
	for(int i=1; i<=n; i++)
		cout<<ans[i]<<" ";
	return 0;
}