第K短路径

题目描述:

一个有向图有n个点，m条边，给出起点s和终点t，求从s到t的第k短路的长度，路径允许重复经过点或边。

输入格式:

第一行，包括两个整数n、m。结点编号依次从1到n编号。

接下来m行，每行包含3个整数 A, B 和 T (1 <= A, B <= N, 1 <= T <= 100)，表示从A点到B点长度为T。

最后一行包括三个整数 S, T 和 K (1 <= S, T <= N, 1 <= K <= 1000)。

输出格式:

一个整数，表示第k短的路径长度，如果不存在，输出-1。

样例输入:

2 2
1 2 5
2 1 4
1 2 2

样例输出:

14

提示:

1 <= N <= 1000, 0 <= M <= 100000

1 <= S, T <= N, 1 <= K <= 1000

时间限制: 1000ms
空间限制: 256MB

---