#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int h[10001],zd[1000001],qz[1000001],nxt[500001],cnt=0;
int dis[10001];
bool flag[10001];
void add(int u,int v,int val)
{
	cnt++;
	zd[cnt]=v,qz[cnt]=val,nxt[cnt]=0;
	nxt[cnt]=h[u];
	h[u]=cnt;
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int ta,tb,tc;
		cin>>ta>>tb>>tc;
		add(ta,tb,tc);
	}
	memset(dis,-1,sizeof(dis));
	memset(flag,0,sizeof(flag));
	dis[s]=0;
	while(1)
	{
		int mv=-1,mi=-1;
		for(int i=1;i<=n;i++)
			if(!flag[i]&&dis[i]!=-1&&(mv==-1||mv>dis[i]))
				mv=dis[i],mi=i;
		if(mv==-1)	break;
		flag[mi]=1;
		for(int p=h[mi];p!=0;p=nxt[p])
		{
			int v=zd[p],val=qz[p];
			if(flag[v]==0&&(dis[v]==-1||dis[v]>dis[mi]+val))
				dis[v]=dis[mi]+val;
		}
	}
	for(int i=1;i<=n;i++)	cout<<dis[i]<<" ";
	return 0;
}