Background

话说数年一度的武林盛事“华山论剑”将至，东邪、西毒、南帝、北丐，老顽童等高手云集华山之巅，誓要分出究竟谁是武林至尊……

Description

如此武林盛世，当然求围观。据统计，有n-1位同学想去华山看热闹，他们分别住在编号为1-n(除华山所在地x)的地方，华山编号为x(1<=x<=n)。现在有M(1<=m<=100000)条有向道路，每条路长为ti(1<=ti<=100)。
由于每位同学看完打架后还要回家吃饭，所以要选择最短路径，求这n-1位同学的最短路径（一个来回）中最长的一条的长度。
特别提醒：可能有权值不同的重边。
数据保证每位同学均能到达华山处，并从华山返回。

Format

Input

第1行： n,m,x；
第2~m+1行: ai,bi,ti,表示有一条从ai到bi的路，长度为ti.

Output

输出仅一行，为最长最短路的长度。

Sample 1

Input

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

Output

10

Limitation

1s, 131072KiB for each test case.

Hint

对于60%的数据，满足 1<=n<=100
对于100%的数据，满足 1<=n<=1000。

Source

tywz