Migrated from Lutece 2728 刺杀卷卷国王

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

卷卷国与摆摆国之间正在发动战争！

为了使世界摆脱内卷，让人们过上幸福快乐的生活，作为摆摆国刺客的你，决定刺杀卷卷国国王！我们可以把卷卷国与摆摆国的世界看做一张 $n$ 个点 $m$ 条边的带权有向图，摆摆国位于 $1$ 号节点，卷卷国位于 $n$ 号节点。根据计划，你从摆摆国出发，沿最短路前往卷卷国施行刺杀。可惜卷卷国的势力过于深入，到处都是卷卷国的眼线，你的计划被发现了！你被迫更改计划绕路前进。根据经验，你判断沿第 $k$ 短路进行刺杀最安全，然后你需要计算这种方案需要走多远。

一句话题意：给你一张 $n$ 个节点 $m$ 条边的带权有向图。现在他想知道从 $1$ 号节点开始，到 $n$ 号节点的第 $k$ 短路长度，数据保证第 $k$ 短路存在。两条路径被视为不同，当且仅当它们经过的边数不同或经过的某条边编号不同

Input

第一行读入三个整数，$n,m,k$，如题目表述

接下来 $m$ 行，每行三个整数，第 $i$ 行读入 $u_{i},v_{i},val_{i}$ 分别代表一条边的起点，终点和边权。

Output

输出第 $k$ 短路长度

Samples

4 6 5 
1 2 1
2 1 5
1 3 3 
2 3 2
3 4 3
1 2 4

12

Constraints

$n\le 5\cdot10^{3},\ m\le 2\cdot10^{5},\ k\le 5\cdot10^{5}$ $u_{i},v_{i}\le n,\ val_{i}\le 10^{3}$

Resources

2022, 2023 UESTC ICPC Training for Graph