#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--;//堆中元素数量-1 
	DuihuaDown();//维护小根堆 
	return;
}

int vis[N]/*标记数组*/,dix[N];
void dijkstra() //迪杰斯特拉算法 
{
	for(int i=1; i<=n; i++)dix[i]=INF;//初始化 
	dix[s]=0;
	memset(vis, 0 ,sizeof(vis));//初始化
	node2 p;
	p.u=s,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;
			if(dix[v]>dix[x]+edge[i].w){
				dix[v]=dix[x]+edge[i].w;//核心 
				p.w=dix[v];
				p.u=v;
				Add(p);//入堆 
			}
		}
	}
}
int main() {
	//std::ios::sync_with_stdio(0);
	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;
}