Migrated from Lutece 1987 童心未泯的帆宝和乐爷

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

6·1即将来临，游乐园推出了新的主题活动，雨过天晴，帆宝和乐爷童心未泯，准备一探究竟。

兴奋的他们一入园便和孩子们打成一片，不知不觉便走散了。

当他们意识到的时候，只能通过手机来确认对方的位置。

他们当然想尽快找到对方，然而由于孩子们实在是太多，只能选择距离稍远的但是游客稀少的路会合。

帆宝希望找到第$k$短的路径，这条路径是他认为的幸运路径。

帆宝迫切地想知道该条路径的长度，而乐于助人的你也一定会帮助她的。

Input

第一行三个整数$n,m,k$，分别表示游乐园的景点数目、景点之间的道路数目以及路径长度从小到大排列时希望选择的序号。

第二行两个整数$S,T$，分别表示帆宝和乐爷所在景点的编号。

接下来$m$行，每行三个整数$u,v,w$，表示编号为$u$和$v$的景点之间有一条长度为$w$的单向通路。

$1\le n \le 1000,0 \le m \le 100000,1 \le k \le 1000,1 \le S,T,u,v \le N,1 \le w \le 100$

Output

第一行一个整数$x$，表示所选路径的长度

无解输出$-1$

Samples

3 3 2
1 2
1 2 2
1 3 4
3 2 1

5

Resources

2018 UESTC ACM Training for Search Algorithm and String