Problem C: Remmarguts' Date
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：19
Solved：15
Description
“好男人从来不会让女孩子等待或破坏约会！”鸳鸯爸爸说。他轻轻地摸了摸小鸭子的头，给它们讲了一个故事。
“雷玛格茨王子住在他的王国UDF——自由联合三角洲。有一天，他们的邻国派Uyuw公主去执行外交任务。
“埃雷诺，公主给雷玛格特写了一封信，告诉他，她愿意来大厅与UDF进行商业谈判，前提是且仅当Uyuw通过第k最短的路径去见王子。（事实上，Uyuw根本不想来）“
对贸易发展感兴趣，而且有这么可爱的女孩，雷玛古特王子真的迷上了。他需要你——首相的帮助！
详细信息：UDF的首都由N个车站组成。大厅编号为S，而编号为T的车站表示王子现在的位置。M泥泞的侧向连接一些车站。公主的路径可能包括同一车站两次或两次以上，即使是数字为S或T的车站。
“雷玛格茨王子住在他的王国UDF——自由联合三角洲。有一天，他们的邻国派Uyuw公主去执行外交任务。
“埃雷诺，公主给雷玛格特写了一封信，告诉他，她愿意来大厅与UDF进行商业谈判，前提是且仅当Uyuw通过第k最短的路径去见王子。（事实上，Uyuw根本不想来）“
对贸易发展感兴趣，而且有这么可爱的女孩，雷玛古特王子真的迷上了。他需要你——首相的帮助！
详细信息：UDF的首都由N个车站组成。大厅编号为S，而编号为T的车站表示王子现在的位置。M泥泞的侧向连接一些车站。公主的路径可能包括同一车站两次或两次以上，即使是数字为S或T的车站。
Input
第一行包含两个整数 N 和 M （1 <= N <= 1000， 0 <= M <= 100000）。站点编号从 1 到 N。以下 M 行中的每一行都包含三个整数 A、B 和 T（1 <= A、B <= N、1 <= T <= 100）。它表明，从A站到B站有一个定向侧向，时间T.
最后一行由三个整数S，T和K组成（1<= S，T<= N，1<= K<= 1000）。
最后一行由三个整数S，T和K组成（1<= S，T<= N，1<= K<= 1000）。
Output
由单个整数组成的单行：第 K 个最短路径（所需时间）。如果第 K 个最短路径不存在，则应改为输出“-1”（不带引号）。
Sample Input Copy
2 2
1 2 5
2 1 4
1 2 2Sample Output Copy
14