### 问题描述 热心公益的G哥哥又来举办慈善晚会了，这次他邀请到了巴菲特、马云等巨富，还邀请到了大V、小C等算法界泰斗。晚会一共邀请了 $n$ 位尊贵的客人，每位客人都位于不同的城市，也就是说每座城市都有且仅有一位客人。这些城市的编号为 $1,2,...,n$，G哥哥决定将晚会放在 $p$ 城市举办。 城市之间有 $m$ 条单向的交通路径（两座城市间可能同时存在多条直接相连的路径），通过每一条路的花费时间为 $t_i$ 。这些客人都日理万机，工作繁忙，因此他们会选择时间最短的路径往返 $p$ 城市，G哥哥想知道客人中花费时间最长的人需要在路上花费多久。 ### 输入格式 第一行三个正整数 $n, m, p$。 接下来 $m$ 行，每行三个整数 $u_i, v_i, t_i$，分别表示一条交通路径的起点，终点和用时。 输入保证图是强连通的，即所有客人都能往返 $p$ 城市。 ### 输出格式 输出一行一个整数，表示花费时间最久的客人所需的时间。 ### 样例输入 ``` 4 7 2 1 3 2 3 4 4 4 2 3 1 4 7 1 2 4 2 3 5 3 1 2 ``` ### 样例输出 ``` 12 ``` ### 评测数据规模 对于 $100$% 的评测数据，$1\leq n \leq 10^3, n\leq m\leq 10^5,1\leq u_i,v_i, p\leq n,1 \leq t_i \leq 100$。