123456798

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9,N=1e3;
int n,m,x;
int g[N][N];
int d[N];
bool v[N];
void spfa(int v0){
    queue<int> q;
    memset(d,0x3f,sizeof d);
    memset(v,false,sizeof v);
    d[v0]=0;//初始化为零
    q.push(v0);//v0入队
    v[v0]=1;
    while(!q.empty()){
        int t=q.front();
        q.pop();
        v[t]=0;
        for(int i=1;i<=n;i++){
            if(g[t][i]==0){
                continue;
            }
            if(d[i]>d[t]+g[t][i]){
                d[i]=d[t]+g[t][i];
                if(!v[i]){
                    v[i]=1;
                    q.push(i);
                }
            }
        }
    }
}
int main(){
    cin>>n>>m>>x;
    for(int i = 1;i <= m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        if(g[u][v]==0){
            g[u][v]=w;
        }else{
            g[u][v]=min(g[u][v],w);
        }
    }
    int s=-99999;
    for(int i = 1;i <= n;i++){
        int sum=0;
        if(i==x){
            continue;
        }
        spfa(i);
        sum+=d[x];
        spfa(x);
        sum+=d[i];
        s=max(sum,s);
	}
    cout<<s;
    return 0;
}