UDF 的首都由 N 个车站组成。大厅编号为 S，而编号为 T 的车站表示王子当前所在地。M 个泥泞的有向边连接了一些车站。雷马古茨迎接公主的路径可能包括同一车站两次或多次，甚至是编号为 S 或 T 的车站。相同长度的不同路径将被视为不同的路径。

第一行包含两个整数 N 和 M（1 \le N \le 1000，0 \le M \le 100000）。车站从 1 到 N 编号。

接下来的 M 行中，每行包含三个整数 A，B 和 T（1 \le A, B \le N，1 \le T \le 100）。它表示从 A 号车站到 B 号车站有一条时间为 T 的有向边。

最后一行由三个整数 S，T 和 K（1 \le S, T \le N，1 \le K \le 1000）组成。

一行，包含一个整数：使用第 K 个最短路径迎接乌玉公主所需的长度（时间）。如果第 K 个最短路径不存在，则应输出 -1（不带引号）。

• 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