There are N communication base stations in the suburbs, P two-way cables, and the i cable connects the base stations Ai and Bi.

In particular, base station 1 is the main station of the communication company, and base station N is located in a farm.

Now, the farmer wants to upgrade the communication line, and upgrading the i Cable Costs Li.

The telephone company is holding a discount.

Farmers can specify a path from base station 1 to base station N, and specify no more than K cables on the path, and the telephone company will provide upgrade services free of charge.

Farmers only need to pay for upgrading the most expensive cable among the remaining cables on the path.

Ask at least how much money can be used to complete the upgrade.

Input format

Line 1: three integers N, P, K.

Section 2 Line P + 1: line i+1 contains three integers AI, Bi and Li.

Output format

Contains an integer indicating the least cost.

If there is no path between base station 1 and base station N, output − 1.

Data range

0≤K<N≤1000,
1≤P≤10000,
1≤Li≤1000000

Input sample:

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

Output example:

4

There is an undirected graph with n points and m edges. It also has k free path opportunities to find the minimum value of the largest edge in all paths from point 1 to point n.

Analysis: finding the shortest path on the layered graph is [shortest path in layered map] flight route: Luogu P4568 In the upgraded version of this problem, the flight route only needs to find the remaining path length under k free paths, which is very easy to obtain. However, this problem requires the minimum value of the k+1 largest side on all paths from 1 to n, which is a bit similar to the shortest path deformation problem, but everything is based on the hierarchical graph. The number of layers on the layered graph indicates that several free paths are used to reach a certain point, and then combined with the idea of the shortest path deformation, this problem is to find the minimum value of the maximum edge on all paths from 1 to n on layer k. just modify the dijkstra relaxation condition as follows:

if(dis[to][c] > max(dis[now][c], e[i].w))
{
    dis[to][c] = max(dis[now][c], e[i].w);
    a.push(make_pair(dis[to][c], to+c*n));
}

Then run a dijkstra on the hierarchical graph, and then count the minimum value of dis[n][i].

The specific codes are as follows:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#define int long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
//Find the minimum value of the k+1 largest side on all paths from 0 to n-1 
//That is, the minimum value of the largest edge on all paths from 0 to n-1 on layer k 
int n, m, k, head[1005], dis[1005][1005], cnt;//dis[i][j] indicates that j free paths were used when I arrived 
bool vis[1005][1005];
struct edge
{
	int to, next, w;
}e[20005];

void add(int u, int v, int w)
{
	e[++cnt].to = v;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}

void dijkstra()
{
	memset(dis, 0x3f, sizeof dis);
	dis[0][0] = 0;
	priority_queue<pii, vector<pii>, greater<pii> > a;
	a.push(make_pair(dis[0][0], 0));
	while(a.size())
	{
		int now = a.top().second;
		int c = now/n;//On which floor 
		now %= n;
		a.pop();
		if(vis[now][c]) continue;
		vis[now][c] = true;
		for(int i = head[now]; i; i = e[i].next)
		{
			int to = e[i].to;
			if(dis[to][c] > max(dis[now][c], e[i].w))
			{
				dis[to][c] = max(dis[now][c], e[i].w);
				a.push(make_pair(dis[to][c], to+c*n));
			}
		}
		if(c < k)
			for(int i = head[now]; i; i = e[i].next)
			{
				int to = e[i].to;
				if(dis[to][c+1] > dis[now][c])
				{
					dis[to][c+1] = dis[now][c];
					a.push(make_pair(dis[to][c+1], to+n*(c+1)));
				}
			}
	}
}

signed main()
{
	cin >> n >> m >> k;
	for(int i = 1; i <= m; i++)
	{
		int u, v, w;
		scanf("%lld%lld%lld", &u, &v, &w);
		u--, v--;
		add(u, v, w), add(v, u, w);
	}
	dijkstra();
	//The minimum value of enumeration is because it may reach 0 in less than k free paths. After that, it will be 0 in half and not 0 in the other half 
	int ans = inf;
	for(int i = 0; i <= k; i++)
		ans = min(dis[n-1][i], ans);
	if(ans == inf)
		puts("-1");
	else
		cout << ans << endl;
    return 0;
}