Professor Floyd and Professor Dijkstra hate each other. After the university moved to a newly built campus, they demanded offices in buildings that were as far away from each other as possible. You are tasked with finding the distance between two such buildings.
In other words, it is required to find two buildings, the shortest path between which is the longest among all pairs of buildings, and print the length of this path. Since the professors sometimes still need to meet, the path between the selected buildings must exist.
Input
The first line contains two numbers N and M - the number of buildings and the number of roads connecting the buildings (1<=N<=100, 0<=M<= (N(N−1))/2. Next, M lines contain descriptions roads: 3 integers si, ei, li - buildings where the road starts and ends and the length of the road, respectively (1< =si, ei<=N, 0<=li<=100, roads are bidirectional).
Output
It is necessary to display one number - the required distance.