#1065. jwp的慈善晚会

内存限制:512 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: lenijwp

题目描述

热心公益的jwp又来举办慈善晚会了,这次他邀请到了巴菲特、马云等巨富,还邀请到了cyy、wzk等算法界泰斗。晚会一共邀请了 位尊贵的客人,每位客人都位于不同的城市,也就是说每座城市都有且仅有一位客人。这些城市的编号为 ,jwp决定将晚会放在 城市举办。

城市之间有 单向的交通路径(两座城市间可能同时存在多条直接相连的路径),通过每一条路的花费时间为 。这些客人都日理万机,工作繁忙,因此他们会选择时间最短的路径往返 城市,jwp想知道客人中花费时间最长的人需要在路上花费多久。

输入格式

第一行三个正整数

接下来 行,每行三个整数 ,分别表示一条交通路径的起点,终点和用时。

输入保证图是强连通的,即所有客人都能往返 城市。

输出格式

输出一行一个整数,表示花费时间最久的客人所需的时间。

样例

样例输入

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

数据范围与提示