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

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

输入格式
第一行包含两个整数N和M。

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

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

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

数据范围
1≤S,T≤N≤1000,
0≤M≤105,
1≤K≤1000,
1≤L≤100
输入样例：
2 2
1 2 5
2 1 4
1 2 2
输出样例：
14

A∗ 算法在人工智能中是一种典型的启发式搜索算法
启发中的估价是用估价函数表示的：
h(n) = f(n) + g(n)
其中 f(n) 是节点n的估价函数
g(n) 表示实际状态空间中从初始节点到n节点的实际代价
h(n) 是从n到目标节点最佳路径的估计代价。
另外定义 h’(n) 为n到目标节点最佳路径的实际值。
如果 h’(n) ≥ h(n) 则如果存在从初始状态走到目标状态的最小代价的解
那么用该估价函数搜索的算法就叫 A∗ 算法。

这就是一个简单的 A_star 搜索，然后我们求一下估价函数，也就是每个点到终点的距离，然后按照估价函数和当前的移动距离，排序即可。A_star 和 bfs 十分像，只不过我们加一个排序的权值。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,m,s,t,k,f[N],a[N],b[N],c[N];
int head[N],nex[N],to[N],w[N],tot;
struct node{
	int u,d,fx;
};
bool operator < (node a,node b){
	return a.fx>b.fx;
}
inline void add(int a,int b,int c){
	to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
void dijkstra(){
	priority_queue<pair<int,int> > pq;	pq.push({0,t});
	memset(f,0x3f,sizeof f);	f[t]=0;	int vis[N]={0};
	while(pq.size()){
		auto u=pq.top().second;	pq.pop();
		if(vis[u])	continue;	vis[u]=1;
		for(int i=head[u];i;i=nex[i]){
			if(f[to[i]]>f[u]+w[i]){
				f[to[i]]=f[u]+w[i];	pq.push({-f[to[i]],to[i]});
			}
		}
	} 
}
int a_star(){
	priority_queue<node> pq;	pq.push({s,0,f[s]});
	int vis[N]={0};
	while(pq.size()){
		int u=pq.top().u;	int dis=pq.top().d;	pq.pop();
		if(vis[u]>=k)	continue;	vis[u]++;
		if(vis[u]==k&&u==t)	return dis;
		for(int i=head[u];i;i=nex[i]){
			if(vis[to[i]]<k)
				pq.push({to[i],dis+w[i],dis+w[i]+f[to[i]]});
		}
	}
	return -1;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i]>>b[i]>>c[i];	add(b[i],a[i],c[i]);	
	}
	cin>>s>>t>>k;	if(s==t)	k++;
	dijkstra();	tot=0;	memset(head,0,sizeof head);
	for(int i=1;i<=m;i++)	add(a[i],b[i],c[i]);
	cout<<a_star()<<endl;	
	return 0;
}