题目描述

森林里有 $N$ 只小熊 $(1≤N≤1000)$ 分别居住在森林里的 $N$ 个地点。他们准备到其中一只小熊家里聚会。总共有 $M(1≤M≤100000)$ 条有向道路连接这 $N$ 只小熊的住处，道路 $i$ 需要 $T_i(1≤T_i≤100)$ 单位的时间才能走完。

每只小熊都必须步行去参加聚会，聚会结束后，回到自己的家。每只熊都很懒，因此会选择花费最短时间路线。由于道路是单向的，小熊的返回路线很可能不同于他去聚会的原始路线。

请问，在所有的小熊中，花费时间最长的那只小熊，需要在往返过程中花费多少时间？

输入格式

第 $1$ 行：三个空格分隔的整数，分别为：$N$、$M$ 和 $X$。

第 $2..M+1$ 行：第 $i+1$ 行用三个空格分隔的整数 $(A_i,B_i,T_i)$ 描述了道路 $i$。所描述的道路从第 $A_i$ 只小熊的家走到第 $B_i$ 只小熊的家，需要 $T_i$ 单位时间。

输出格式

输出一个数表示答案。

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

数据规模

居住在 $4$ 处的小熊可以直接前往聚会（$3$ 个单位时间），并经由小熊 $1$ 和 $3$ 的住处（$7$ 个单位时间）返回，总共 $10$ 个单位时间。