Secret Milking Machine Route Optimization

John is designing a secret new milking machine and wants to keep it hidden for as long as possible. To achieve this, he hides the machine on his farm and makes several trips to the machine's location. The farm is divided into N regions (numbered from 1 to N, with N ≤ 200) and connected by P bidirectional roads. Each road has a length L (an integer less than 10⁶), and there can be multiple roads connecting the same pair of regions.

John must travel from the warehouse located in region 1 to the milking machine in region N exactly T times. Note that on his return journey he uses a secret tunnel, so the restriction applies only to the trips from region 1 to region N. To minimize the risk of being discovered, he never uses the same road more than once across all trips. Although he always prefers the shortest route, his objective is different from minimizing the total travel distance. Instead, he wants the longest single road used in each of his trips (i.e. the maximum L encountered on a path) to be as small as possible.

Formally, given T, N, and P along with the details of each road, your task is to determine the smallest possible value X such that there exist T edge-disjoint paths from region 1 to region N where all roads used have length at most X. It is guaranteed that T such paths exist.

Note: All formulas must be expressed in LaTeX format. For example, use \(T\), \(N\), \(P\), and \(L\) to denote the given parameters.

inputFormat

The first line contains three integers \(T\), \(N\), and \(P\), where \(T\) is the number of trips, \(N\) is the number of regions, and \(P\) is the number of roads.

Each of the next \(P\) lines contains three integers \(u\), \(v\), and \(L\), indicating that there is a bidirectional road between regions \(u\) and \(v\) with length \(L\).

outputFormat

Output a single integer representing the minimum possible value \(X\) such that there exist \(T\) edge-disjoint paths from region 1 to region \(N\) with every road on these paths having a length at most \(X\).

sample

1 3 3
1 2 4
2 3 5
1 3 10

5