本关任务：给定一个加权有向图可能权值存在负数找到从给定源到给定目的地的成本最低的路径路径可能重复经过同一个点且该路径恰好有m条边编程要求首先输入图的节点数量n和边的数量e然后依次输入这e条边的信息每条边包含3项内容：顶点1的编号顶点2的编号权值。最后输入source和destination的编号以及路径的边数限制m输出source到destination的成本最低的路径长度并且该路径恰好有m条边。

输入格式: 第一行包含三个正整数，分别表示节点数量n，边的数量e，路径的边数限制m。

接下来e行，每行包含三个整数u、v、w，表示一条有向边从u指向v，权值为w。

最后一行包含两个整数s、t，表示需要找到从s到t恰好有m条边的最短路径。

输出格式: 输出一个整数，表示从s到t恰好有m条边的最短路径长度。如果不存在这样的路径，则输出2147483647。

输入样例1： 4 4 2 1 2 1 2 3 2 3 4 3 4 1 -4 1 3 输出样例1： 2147483647 输入样例2： 4 4 2 1 2 1 2 3 2 3 4 3 4 1 -4 1 4 输出样例2： -1