/ TYWZ / 题库 /

C-sword

C-sword

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

信息

难度
6
分类
(无)
标签
(无)
递交数
50
已通过
14
通过率
28%
上传者

相关

在下列比赛中:

图论之最短路径检测