题目描述

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

输入格式

第一行两个整数 $n,m$，$1\le n\le 1000$，$0\le m\le 10^5$。

接下来 $m$ 行，每行描述一条有向边 $x,y,z$，表示一条从 $x$ 指向 $y$ 的边权为 $z$ 的有向边，$1\le z\le 100$。

最后一行三个整数 $s,t,k$，$1\le k\le 1000$。

输出格式

输出一个整数表示答案。

2 2
1 2 5
2 1 4
1 2 2

14