#include<bits/stdc++.h>
#define inf #include<bits/stdc++.h>
#define inf #include<bits/stdc++.h>
#define inf pow(2,31)-1
using namespace std;
long long m,n,s,u,v,w,min1,next1,ss;
int main()
{
	cin>>n>>m>>s;
	ss=s;
	long long map1[n+5][n+5],dist[n+5],visit[n+5];
	for(int i=1;i<=n;i++)
	{
		visit[i]=1;
		dist[i]=inf;
		for(int j=1;j<=n;j++)
		{
			map1[i][j]=inf;
		}
	}
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		map1[u][v]=w;
	}
	dist[s]=0;
	visit[s]=0;
	while(1)
	{
		min1=inf;
		for(int i=1;i<=n;i++)
		{
			if(map1[s][i]!=inf)
			{
				dist[i]=min(dist[i],map1[s][i]+dist[s]);
			}
			if((visit[i])&&(dist[i]<min1))
			{
				next1=i;
				min1=dist[i];
			}
		}
		if(min1==inf)
		{
			break;
		}
		s=next1;
		visit[s]=0;
	}
	dist[ss]=0;
	for(int i=1;i<=n;i++)
	{
		cout<<dist[i]<<" ";
	}
	cout<<endl;
	return 0;
}

用的是 dijkstra