背景故事

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

题目描述

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

输入格式

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

输出格式

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

样例输入

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

样例输出

10

数据范围

对于 50%的数据，1 <= n <= 100，1 <= m <= 10000；
对于 100%的数据，1 <= n <= 1000,1 <= m <= 100000，1 <= ti <= 1000。

限制

1s

来源

CWOI新高二专题测试⑨