Messenger's Travel Time

You are given a weighted undirected graph that represents a network of cities and roads. The cities are numbered from 1 to N, where city 1 is the capital. Each road connects two distinct cities and has a travel time associated with it. Your task is to compute the maximum travel time from the capital (city 1) to any other city using the shortest paths. In other words, if the shortest distance from city 1 to city i is (d_i), you must output (\max_{1 \le i \le N}{d_i}). If there exists any city that is unreachable from the capital, output -1. Note that if there is only one city (N = 1), the answer is 0.

inputFormat

The input is read from standard input (stdin). The first line contains two integers (N) and (M): the number of cities and the number of roads, respectively. Each of the next M lines contains three integers (u), (v), and (t) indicating that there is a road between cities (u) and (v) with travel time (t).

outputFormat

Output a single integer representing the maximum travel time from the capital to all cities using the shortest paths. If there is any city that is unreachable, output -1.## sample

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

8