题目描述

时光荏苒,光阴似箭,日月如梭,秋风瑟瑟。额,总感觉好熟悉的一句话啊……

你尽了很大的努力,但很不幸得是,妹子还木有“圈”到,却由于装13的企图太过明显,你被一个名为“Ga-Ysh-Yf-001"的国际组织盯上了,”组织“不能容忍你这样的Loser去追女生(因为你可是Loser,“组织”里的人木有追到,你要是追到了,“组织”会心理不平衡么),于是,他们决定等你放学去“圈”你。为了防止世界被破坏!为了维护世界的和平!贯彻爱与真实的邪恶!你不能被他们圈到!所以你要想办法尽快的逃离学校!

你的学校和你家所在的图上共有R条路,连接了N个地点,学校坐落于地点1,你家坐落于地点N,每条路有一固定的长度,在你移动速度恒定的情况下你要想办法以最快的速度回到家里。但是"组织"不会让你这么容易就回家的,他们利用了你迫切的心情,在路上做了些手脚。“S**党”在“组织”中的间谍之一(代号Cys)发来的秘密消息中不明缘由的指示你道,你要严格确保自己的走的路径总长度不是前K短的,否则后果会不堪设想。

因此请你计算出第K+1短的路径长度,然后尽快回家,长度相同的路径视为一条,同一条路可以经过多次。

输入格式

第1行: 三个整数,N(1<=N<=5000),R(1<=R<=100,000),k(k<=6),用空格隔开。

第2..R+1行: 每行包含三个用空格隔开的整数A、B和D,表示存在一条长度为

D(1 <= D <= 5000)的路连接地点A和地点B。

输出格式

仅一行,第k+1短路径的长度。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论