题目描述

“好男人从来不让女孩等待或中断约会!””普通话鸭子父亲说。轻轻地抚摸着小鸭子的脑袋,他给他们讲了一个故事。

雷马古特亲王住在他的王国UDF - 自由三角洲联合三角洲。有一天,他们的邻国派他们为乌尤公主执行外交任务。

“现在,公主给雷马古特斯发了一封信,告诉他,如果王子去通过$K-thstimalth$路径去见她,她才会来大厅和UDF举行商业会谈。

对贸易发展和这样一个可爱的女孩感兴趣,雷马古茨王子真的爱上了。他需要你——总理的帮助!

详细信息$:UDF$的首都由$N$站组成。大厅编号为S,而编号为T的车站表示王子的当前位置。$M muddy$ 定向侧向连接一些车站。$Remmarguts$欢迎公主的路径可能包括同一站两次或两次以上,即使是号码为S或T的车站。具有相同长度的不同路径将被视为不同。

输入

第一行包含两个整数$N$和$M(1 <= N <= 1000,0 <= M <= 100000)$车站编号为1至N。以下每行包含三个整数$A,B和T(1 <= A,B <= N,1 <= T <= 100)$。这表明有一个从$A-th$站到$B-th$站的定向侧路,时间为$T$。

最后一行由三个整数$S,T$和$K(1 <=S,T<=N,1<=K<=1000)$组成。

输出

由单个整数组成的单行:使用$K-thstimal$路径欢迎$Princess Uyuw$的长度(所需时间)。如果$K-th stimalt$ 路径不存在,则应输出$“-1”$(无引号)。 输入数 1

2 2
1 2 5
2 1 4
1 2 2

输出数位 1

14

来源

POJ 月刊, 朱泽苑