题目描述

有 $n$ 个城市和 $m$ 条单向道路，城市编号为 $1$ 到 $n$ 。

给定两个城市 $a$ 和 $b$ ，请求出从 $a$ 城市到 $b$ 城市的第 $k$ 短路的长度。（允许经过重复的点或者边）

输入

第一行有四个整数 $n$ , $m$ , $a$ , $b$ , $k$ 。($1≤n≤1000$ , $0≤m≤10000$ , $1≤a,b≤n$ , $a \neq b$ , $1≤k≤1000$)。

接下来 $m$ 行，每行有 $3$ 个整数 $x$,$y$,$l$ ，表示 $x$ 到 $y$ 之间有一条长为 $l$ 的道路。（ $1≤x,y≤n$,$1≤l≤100$ ）。

输出

输出第 $k$ 短路的长度，不存在第 $k$ 短路，请输出 $-1$ 。

样例

3 3 1 3 2
1 2 1
2 3 1
1 3 2

2

来源

POJ