#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
struct node
{
	int poi,len;
};
int n,m,s;
vector<node> mp[10005];
int len[10005];
int vis[10005];
bool is[10005];
queue<int> q;
bool spfa(int s)
{
	for(int i = 1; i <= 10000; i++)len[i]=2147483647;
	q.push(s);
	is[s]=1;
	len[s]=0;
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		vis[t]++;
		is[t]=0;
		for(int i = 1; i <= (int)mp[t].size(); i++)
		{
			if(mp[t][i].len+len[t]<len[mp[t][i].poi])//这一行RE
			{
				len[mp[t][i].poi]=mp[t][i].len+len[t];
				if(!is[len[mp[t][i].poi]])
				{
					q.push(len[mp[t][i].poi]);
					is[len[mp[t][i].poi]]=1;
					vis[len[mp[t][i].poi]]++;
					if(vis[len[mp[t][i].poi]]>m)return 0;
				}
			}
		}
	}
	return 1;
}

int main()
{
//	freopen("testin.txt","r",stdin);
//	freopen("testout.txt","w",stdout);
	cin >> n >> m >> s;
	for(int i = 1; i <= m; i++)
	{
		int a,b,c;
		cin >> a >> b >> c;
		mp[a].push_back({b,c});
	}
	spfa(s);
	for(int i = 1; i <= n; i++)
	{
		cout << len[i] << " ";
	}
	return 0;
}

附评测结果