题目描述

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

输入格式

第一行包含两个整数$\red{N}$和$\red{M}$。

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

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

输出格式

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

样例

输入样例

2 2
1 2 5
2 1 4
1 2 2

输出样例

14

提示

$\red{1≤S,T≤N≤1000}$,

$\red{0≤M≤10^5}$,

$\red{1≤K≤1000}$,

$\red{1≤L≤100}$

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