#include <bits/stdc++.h>
using namespace std;
const int Inf=1e9;
const int maxn=2e5+5;
int n,m,s;
int f[5500][5500],dis[maxn]={Inf};
bool flag[maxn];
int main()
{
	cin>>n>>m>>s;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			f[i][j]=Inf;
	for(int i=1; i<=m; i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		f[x][y]=w;
	}
	for(int i=1; i<=n; i++)
		dis[i]=f[s][i];
	dis[s]=0;
	flag[s]=true;
	for(int i=1; i<n; i++)
	{
		int k=0;
		for(int j=1; j<=n; j++)
			if(dis[k] > dis[j] && !flag[j])
				k=j;
		flag[k]=true;
		for(int j=1; j<=n; j++)
			if(!flag[j])
				dis[j]=min(dis[j],dis[k]+f[k][j]);
	}
	for(int i=1; i<=n; i++)
		cout<<dis[i]<<' ';
	return 0;
}