Jiahai the greedy mayor has recently entered another PotatoTown to monopolise its economy. In order to do that, Jiahai has decided to build a mega potato farm and become the world's largest exporter of potato! Since birth, these potatoes will be enslaved to work in large Pringles factories, their whole lives spent killing their fellow potatoes, and at the end of this cruel journey, the potatoes themselves will be put into Pringles cans and sold. Muahahahaha!
Jiahai being the cruel potato slave master he is, has come up with a plan to enslave the entire world's population of potatoes into his potato farm. However, Jiahai knows that these tough conditions will result in these potatoes attempting to escape. As a result, he would like to delay their escape as much as possible if any dare try. In order to do so, he wants to build the potato farm as far as possible from the entrance of the city, such that the shortest path from the potato farm to the entrance of the city is maximised.
He will be given a map of the city with N road intersections and E roads between any two road intersections. Jiahai the greedy mayor has also built the road such that there is only one unique path from any road intersection to another, in order to save cost. Given the map of the city, help Jiahai determine the maximum distance the potatoes have to run in order to escape if he chooses the positions of these two locations optimally.
The first line of input will contain two integers, N
The next E
lines of input will contain three integers each, describing a road, the first two being the road intersection that the road joins and the last being the length of the road.
Your output should contain one integer, the maximum distance the potatoes have to run to escape if the positions of the farm and entrance are optimal.
For all subtasks: All road lengths will be less than 1000.
Subtask 1 (10%): 1 ≤ N, E ≤ 20.
Subtask 2 (20%): 1 ≤ N, E ≤ 300.
Subtask 3 (30%): 1 ≤ N, E ≤ 5 000.
Subtask 4 (40%): 1 ≤ N, E ≤ 100 000.
Subtask 5 (0%): As per sample testcases.
Sample Input 1
0 1 1
1 2 1
2 3 1
3 4 5
Sample Output 1