题目描述

给定一张 $N$ 个点（编号 $1,2…N$），$M$ 条边的有向图，求从起点 $S$ 到终点 $T$ 的第 $K$ 短路的长度，路径允许重复经过点或边。

注意：每条最短路中至少要包含一条边。

输入格式

第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行包含三个整数 $A,B$ 和 $L$，表示点 $A$ 与点 $B$ 之间存在有向边，且边长为 $L$。

最后一行包含三个整数 $S,T$ 和 $K$，分别表示起点 $S$，终点 $T$ 和第 $K$ 短路。

输出格式

输出占一行，包含一个整数，表示第 $K$ 短路的长度，如果第 $K$ 短路不存在，则输出 $-1$。

样例

输入样例：

2 2
1 2 5
2 1 4
1 2 2

输出样例：

14

样例解释

图有 $N=2$ 个点，$M=2$ 条边：

• $1 \to 2$，长度 5
• $2 \to 1$，长度 4

起点 $S=1$，终点 $T=2$，求第 $K=2$ 短的路径。

可能的路径：

1. $1 \to 2$，长度 5（第一短）
2. $1 \to 2 \to 1 \to 2$，长度 5+4+5=14（第二短）

所以输出 14。

数据范围

• $1 \le S, T \le N \le 1000$
• $0 \le M \le 10^4$
• $1 \le K \le 1000$
• $1 \le L \le 100$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB