该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

HD Remake War3 魔兽争霸3

题目描述

Richie的爸爸曾经很喜欢玩一个游戏叫《魔兽争霸3》。最近暴雪公司宣布重做HD版的《魔兽争霸3》上架，小Richie想和爸爸来一局对战。爸爸说，你做一个题先。做不出来别想玩。题目是这样的：

Richie的爸爸在玩《魔兽争霸3》，由于久疏战阵，想开分矿的时候，发现现在木头是0，而开分基地要K个木头。还好Richie的爸爸在森林边建立了多个伐木场，伐木场之间有双向道路连接，（伐木场可以和自己连接），这些伐木场标记为1号到N号。当农民走过一家伐木场，就会收集到10个木头。于是派农民从S号伐木场出发去采木头，顺便去伐木场T建立分基地 。

现在请你帮忙计算一下，完成开分基地最少还要多久（包括收集木材和放下分基地）如果不能完成，则输出 -1。

输入

第一行有两个整数N (1<=N<=5000) M (0<=M<=100000)代表伐木场的个数和路径的条数。

接下来的M行每行有三个整数A B C (1<=A B<=N; 1<=C<=100)，表示存在一条路径连接着A伐木场和B伐木场，经过这一条路需要花费C时间。

最后一行有三个整数S T K (1<=S T<=N; 0<=K<=500)，是对应问题描述中的S T K。

输出

每个样例输出一行答案

样例输入

4 4
1 2 1
2 3 2
1 3 100
3 4 1
1 3 50

样例输出

7