#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int next,to,w;
}edge[100];
int cnt=0,n,m,tn,tt,tw,head[100],p[100],_min;
bool vis[100];
void add(int next,int t,int w)
{
	edge[cnt].w=w;
	edge[cnt].to=t;
	edge[cnt].next=head[next];
	head[next]=cnt;
	cnt++;
}
void dij(int start)
{
	if(vis[start])return;
	vis[start]=true;
	_min=head[start];
	for(int i=head[start];i!=-1;i=edge[i].next)
	{
		if(edge[i].w<edge[_min].w)_min=i;
		p[edge[i].to]=p[edge[i].to]>p[start]+edge[i].w?p[start]+edge[i].w:p[edge[i].to];
	}
	dij(_min);
}
int main()
{
	memset(head,-1,sizeof(head));
	memset(vis,false,sizeof(vis));
	memset(p,0x3f,sizeof(p));
	cin>>n>>m>>tn;
	for(int i=0;i<m;i++)
	{
		cin>>tn>>tt>>tw;
		add(tn,tt,tw);
	}
	p[tn]=0;
	dij(tn);
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])dij(i);
	}
	for(int i=1;i<=n;i++)
	{
	    cout<<p[i]<<" ";
	}
	return 0;
}