Minimum Maximum Difficulty Route

You are given a road network with N intersections labelled from 1 to N and M bidirectional trails. Each trail connects two intersections and has an associated difficulty level. In addition, you are given an integer D which represents the maximum allowed difficulty for any single trail in the route.

Your task is to find a route from intersection 1 to intersection N such that every trail on the route has a difficulty less than or equal to D, and among all such routes, the maximum difficulty encountered on any single trail is minimized. In mathematical terms, if a valid route uses trails with difficulties \(d_1, d_2, \dots, d_k\), you need to minimize \(\max(d_1, d_2, \dots, d_k)\). If no such route exists, output \(-1\).

Note: You may assume that the input describes a valid network and that intersections are numbered consecutively from 1 to N.

inputFormat

The input is given via standard input and has the following format:

N M D
u1 v1 w1
u2 v2 w2
...
uM vM wM

Where the first line contains three integers:

• N - the number of intersections (nodes).
• M - the number of trails (edges).
• D - the maximum allowed difficulty for any trail on the route.

Each of the next M lines contains three space-separated integers \(u_i\), \(v_i\) and \(w_i\) that represent a trail connecting intersections \(u_i\) and \(v_i\) with a difficulty level \(w_i\>.

outputFormat

Output a single integer via standard output representing the minimum possible value of the maximum difficulty on any trail along a valid route from intersection 1 to intersection N. If no valid route exists, output \(-1\).

## sample

4 5 5
1 2 4
1 3 2
2 4 5
3 4 6
2 3 3

5