原题

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef long long ll;
#define x first
#define y second
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, int> PII;
int s, t, k, n, m, u, v, z;
struct node
{
	int v;
	int len;
};
vector<node> mp[1010], mp_dij[1010];
int dist[1010];
bool vis[1010];
int cnt;
void dij()
{
	priority_queue<PII, vector<PII>, greater<PII> > q;
	q.push({0, t});
	memset(dist, 0x3f, sizeof dist);
	dist[t] = 0;
	while(q.size())
	{
		int u = q.top().y;
		q.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(auto it : mp_dij[u])
		{
			int v = it.v;
			if(dist[v] > dist[u] + it.len) dist[v] = dist[u] + it.len, q.push({dist[v], v});
		}
	}
}
int A_star()
{
	priority_queue<PIII, vector<PIII>, greater<PIII> > q;
	q.push({dist[s], {0, s}});
	while(q.size())
	{
		PIII cur = q.top();
		q.pop();
		int u = cur.y.y;
		int dis = cur.y.x;
		if(u == t) cnt ++;
		if(cnt == k) return dis;
		for(auto it : mp[u])
		{
			int v = it.v;
			q.push({dis + it.len + dist[v], {dis + it.len, v}});
		}
	}
	return -1;
}
int main()
{
	IOS;
	cin >> n >> m;
	for(int i = 0; i < m; i ++) cin >> u >> v >> z, mp_dij[v].push_back({u, z}), mp[u].push_back({v, z});
	cin >> s >> t >> k;
	if(s == t) k ++;
	dij();
	cout << A_star();
	return 0;
}