405560: GYM101992 H Find the path

You are given a weighted connected undirected graph of N nodes and M edges (with no self-loops or multiple edges). Additionally, you have three integers u, L and K.

Your task is to find all paths of length L edges that start from node u, and for each path of them you need to sort the weights on its edges in an ascending order and report the weight in the K_th position, what is the maximum value among all the values you report?

Please note that an edge can appear in the same path multiple times, which means that paths don't have to be simple, read the 'Notes' section for more clarification.

The first line of the input contains a single integer T the number of test cases. Each test case starts with a line containing five integers N, M, u, L and K, where 2 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁵, 1 ≤ u ≤ N, 1 ≤ L ≤ 10⁵ and 1 ≤ K ≤ L.

The next M lines represent the edges in the graph where each line contains three integers u, v and w to indicate an edge with weight w between nodes u and v, where 1 ≤ w ≤ 10⁹, 1 ≤ u ≤ N, 1 ≤ v ≤ N and u ≠ v.

For each test case output a single line with the maximum value.

2
5 5 2 7 2
2 1 71
2 3 88
2 4 50
1 5 95
4 3 104
2 1 2 100 70
2 1 7

104
7

In the paths you can visit the same edge or node more than one time.