#include<iostream>
#include<queue>
using namespace std;
struct node{
   int x,y,val;
};
node gra[10010];
long long dis[10010];
bool vis[10010];
int cnt[10010];
int n,m,s;
bool SPFA()
{
   for(int p=1;p<=n;p++)
   	dis[p]=2147483647;
   dis[s]=0;
   queue<int>que;
   que.push(s);
   while(!que.empty())
   {
   	int fr=que.front();
   	que.pop();
   	vis[fr]=0;
   	cnt[fr]++;
   	if(cnt[fr]>n)
   		return 0;
   	for(int p=0;p<que.size();p++)
   	{
   		if(dis[p]<dis[fr]+gra[p].val)
   		{
   			dis[p]=dis[fr]+gra[p].val;
   			if(!vis[p])
   			{
   				vis[p]=1;
   				que.push(p);
   			}
   		}
   	}
   }
   return 1;
} 
int main()
{
   cin>>n>>m>>s;
   for(int p=1;p<=n;p++)
   	cin>>gra[p].x>>gra[p].y>>gra[p].val;
   SPFA();
   for(int p=1;p<=n;p++)
   	cout<<dis[p]<<' ';
}

萌新刚学最短路，求助TAT