#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define maxn 100010 using namespace std; int n,m,T,num1,num2,head1[maxn],head2[maxn],dis1[maxn],dis2[maxn],f[maxn]; queue<int>q1; queue<int>q2; int ans[maxn],maxx; struct node { int u,v,t,pre; }e1[maxn]; struct Node { int u,v,t,pre; }e2[maxn]; int init() { int x=0;char s;s=getchar(); while(s<'0'||s>'9')s=getchar(); while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x; } void Add1(int from,int to,int dis) { num1++; e1[num1].u=from; e1[num1].v=to; e1[num1].t=dis; e1[num1].pre=head1[from]; head1[from]=num1; } void Add2(int from,int to,int dis) { num2++; e2[num2].u=from; e2[num2].v=to; e2[num2].t=dis; e2[num2].pre=head2[from]; head2[from]=num2; } void SPFA1() { dis1[T]=0; q1.push(T); f[T]=1; while(!q1.empty()) { int k=q1.front(); q1.pop(); f[k]=0; for(int i=head1[k];i;i=e1[i].pre) if(dis1[e1[i].v]>dis1[k]+e1[i].t) { dis1[e1[i].v]=dis1[k]+e1[i].t; if(f[e1[i].v]==0) { f[e1[i].v]=1; q1.push(e1[i].v); } } } } void SPFA2() { dis2[T]=0; q2.push(T); f[T]=1; while(!q2.empty()) { int k=q2.front(); q2.pop(); f[k]=0; for(int i=head2[k];i;i=e2[i].pre) if(dis2[e2[i].v]>dis2[k]+e2[i].t) { dis2[e2[i].v]=dis2[k]+e2[i].t; if(f[e2[i].v]==0) { f[e2[i].v]=1; q2.push(e2[i].v); } } } } int main() { //freopen("sparty.in","r",stdin); //freopen("sparty.out","w",stdout); int x,y,z; n=init();m=init();T=init(); for(int i=1;i<=m;i++) { x=init();y=init();z=init(); Add2(x,y,z);Add1(y,x,z); } memset(dis1,127/3,sizeof(dis1)); memset(dis2,127/3,sizeof(dis2)); SPFA1(); memset(f,0,sizeof(f)); SPFA2(); for(int i=1;i<=n;i++) ans[i]=dis1[i]+dis2[i]; for(int i=1;i<=n;i++) maxx=max(maxx,ans[i]); printf("%d ",maxx); return 0; }