#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
struct node{
	int d,y;
}tmp;
bool operator <(const node &a,const node &b){
	return a.d>b.d;
}
priority_queue <node> q;
const int N=1e5+5,M=2e5+5; 
int v[M],e[M],nxt[M],h[N],d[N],tot;
bool b[N];
void add(int x,int y,int z);
void dijkstra(int s);
int main(){
	int n,m,s;
	scanf("%d%d%d",&n,&m,&s);
	for (int i=1;i<=n;++i){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
	}
	dijkstra(s);
	for (int i=1;i<=n;++i)
		printf("%d ",d[i]);
	return 0;
}
inline void add(int x,int y,int z){
	v[++tot]=y;
	e[tot]=z;
	nxt[tot]=h[x];
	h[x]=tot;
}
inline void dijkstra(int s){
	memset(d,0x3f,sizeof(d));
	d[s]=0;
	tmp.d=0;
	tmp.y=s;
	q.push(tmp);
	while (q.size()){
		int x=q.top().y;
		q.pop();
		if (b[x])
			continue;
		b[x]=1;
		for (int i=h[x];i;i=nxt[i]){
			int y=v[i],z=e[i];
			if (d[y]>d[x]+z){
				d[y]=d[x]+z;
				if (!b[y]){
					tmp.d=d[y];
					tmp.y=y;
					q.push(tmp);
				}
			}
		}
	}
}