Minimize Maximum Road Cost

You are given a graph with (N) cities and (M) bidirectional roads. Each road is described by three integers (u), (v), and (\text{cost}), where the road connects city (u) and city (v) with travel cost (\text{cost}). A path from city 1 to city (N) has a cost defined as the maximum cost among all roads in that path. Formally, for any path (P), the cost is given by (\text{cost}(P)=\max_{e\in P},w(e)). Your task is to find a path from city 1 to city (N) that minimizes (\text{cost}(P)), that is, compute [ \min_{P: 1\rightarrow N} ; \max_{e\in P} ; w(e). ] If there is no valid path from city 1 to city (N), output inf.

This problem requires you to implement an algorithm that efficiently finds the minimal possible maximum road cost along any valid route. A modified version of Dijkstra's algorithm can be used for this purpose.

inputFormat

The input is given via standard input (stdin).\n\nThe first line contains two integers (N) and (M), representing the number of cities and the number of roads, respectively.\nEach of the following (M) lines contains three integers (u), (v), and (\text{cost}), describing a bidirectional road between cities (u) and (v) with a travel cost of (\text{cost}).

outputFormat

Output a single line via standard output (stdout) which contains the minimum possible value of the maximum road cost on a valid path from city 1 to city (N). If there is no path from city 1 to city (N), output inf.## sample

4 5
1 2 4
1 3 3
2 3 2
2 4 7
3 4 1

3