#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2*1e5,INF=1e9+10;
int n,m,s;
struct node {
	int to,nxt,w;
};
node edge[M];
int tot,head[N];
void add(int u,int v,int w) {
	edge[tot].nxt=head[u];
	edge[tot].w=w;
	edge[tot].to=v;
	head[u]=tot;
	tot++;
}
struct node2 {
	int w,u;
};
node2 q[M];
int cnt=0;
void DuihuaDown() {
	int i=1;
	while(1) {
		int m=i;
		if(i*2<=cnt&&q[m].w>q[i*2].w)m=i*2;
		if(i*2+1<=cnt&&q[m].w>q[i*2+1].w)m=i*2+1;
		if(m==i)break;
		swap(q[i],q[m]);
		i=m;
	}
	return;
}
void DuihuaUp(int x) {
	while(x/2>0&&q[x/2].w>q[x].w) {
		swap(q[x],q[x/2]);
		x/=2;
	}
	return;
}
node2 Find() {
	return q[1];
}
void Add(node2 p) {
	cnt++;
	q[cnt]=p;
	DuihuaUp(cnt);
	return;
}
void Del() {
	q[1]=q[cnt];
	cnt--;
	DuihuaDown();
	return;
}

int vis[N],dix[N];
void dijkstra() {
	for(int i=1; i<=n; i++)dix[i]=INF;
	dix[s]=0;
	node2 p;
	p.u=1,p.w=0;
	Add(p);
	while(cnt) {
		p=Find();
		Del();
		int x=p.u;
		if(vis[x])continue;
		vis[x]=1;
		for(int i=head[x]; i!=-1; i=edge[i].nxt) {
			int v=edge[i].to;
			dix[v]=min(dix[v],dix[v]+edge[i].w);
			if(!vis[v]) {
				p.w=dix[v];
				p.u=v;
				Add(p);
			}
		}
	}
}
int main() {
	memset(head,-1,sizeof(head));
	scanf("%d%d%d",&n,&m,&s);

	int u,v,w;
	for(int i=1; i<=m; i++) {
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}

	dijkstra();
	
	for(int i=1;i<=n;i++)cout<<dix[i]<<" ";
	return 0;
}