Description

$给定一个有向图，N 个节点，M 条边。求从源点S 到终点T 的第K 短路。$

$路径可能包含两次或两次以上的同一节点，甚至是S 或T 。$

$具有相同长度的不同路径将被视为不同。$

Format

Input

$第1行包含两个整数N 和M （1≤N ≤1000，0≤M ≤100000）。$

$节点编号为1～N 。以下M 行中的每一行都包含3个整数A 、B和T （1≤A , B ≤N ，1≤T ≤100），表示从A 到B 有一条直达的路径，需要时间T 。$

$最后一行包含3个整数S 、T 和K （1≤S , T ≤N ，1≤K ≤1000）。$

Output

$单行输出第K 短路径的长度（所需时间）。如果不存在第K短路，则输出-1。$

Samples

2 2
1 2 5
2 1 4
1 2 2

14

来源

POJ2449