#2471. 第 K 短路

第 K 短路

Description

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

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

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

Format

Input

1行包含两个整数NM1N10000M100000)。第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个整数STK1S,TN1K1000)。最后一行包含3个整数S 、T 和K (1≤S , T ≤N ,1≤K ≤1000)。

Output

单行输出第K短路径的长度(所需时间)。如果不存在第K短路,则输出1单行输出第K 短路径的长度(所需时间)。如果不存在第K短路,则输出-1。

Samples

2 2
1 2 5
2 1 4
1 2 2
14

来源

POJ2449