$玄{\color{white} 0}关$

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x;
	int w;
};
int n,m,s;
vector<node> e[10005];
int a[10005];
queue<int> q;
void dijkstra(int s)
{
	q.push(s);
	a[s]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<e[u].size();i++)
		{
			node v=e[u][i];
			if(a[v.x]>a[u]+e[u][v.x].w)
			{
				a[v.x]=a[u]+e[u][v.x].w;
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(a,0x3f3f3f3f3f3f,sizeof(a));
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		e[u].push_back({v,w});
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)
	{
		if(a[i]==0x3f3f3f3f3f3f)
		{
			cout<<(1<<31)-1<<' ';
		}
		else
		{
			cout<<a[i]<<' ';
		}
	}
	return 0;
}