J10 实践-10 王子的约会

题目描述

鸭子父亲轻轻地抚摸着他的小鸭子的头，给它们讲了一个故事。

"Remmarguts王子住在他的王国UDF--自由联合三角洲。有一天，他们的邻国给他们送来了尤尤公主的外交任务。"

"Erenow，Uyuw公主给Remmarguts王子写了一封信，告诉他她会来大厅与UDF进行商业谈判，如果而且只有当王子通过 $K-th$ 最短路径去见她。(事实上，Uyuw根本就不想来）"

由于对贸易发展感兴趣，Remmarguts王子需要你的帮助!

详细情况： UDF的首都由 $N$ 个车站组成。大厅的编号是 $S$ ，而编号为 $T$ 的车站表示王子目前的位置。泥泞的道路连接着一些车站。Remmarguts王子迎接公主的路径可能包括两次或两次以上的相同车站，即使是编号为 $S$ 或 $T$ 的车站（ $S$ 和 $T$ 不相等）。

输入格式

第一行包含两个整数 $N$ 和 $M$ 。接下来的 $M$ 行包含三个整数 $A$，$B$ 和 $T$。它表明有一条从 $A$ 站到 $B$ 站的定向侧线，时间为 $T$。

最后一行由三个整数 $S$，$T$ 和 $K$ 组成。

输出格式

一行由一个整数组成：使用第 $K$ 条最短路径欢迎乌尤公主的长度（所需时间）。如果 $K-th$ 最短路径不存在，你应该输出"-1"（不带引号）来代替。

样例输入

2 2
1 2 5
2 1 4
1 2 2

样例输出

14

样例分析

如上所述。

数据范围

对于 $100 \%$ 的数据：$1 \le N \le 1000$，$0 \le M \le 100000$，$1 \le A,B \le N$，$1 \le T \le 100$，$1 \le S,T \le N$，$1 \le K \le 1000$。