CF266D BerDonalds

BerDonalds, a well-known fast food restaurant, is going to open a cafe in Bertown. The important thing is to choose the new restaurant's location so that it would be easy to get there. The Bertown road system is represented by $ n $ junctions, connected by $ m $ bidirectional roads. For each road we know its length. We also know that we can get from any junction to any other one, moving along the roads. Your task is to find such location of the restaurant, that the shortest distance along the roads from the cafe to the farthest junction would be minimum. Note that the restaurant can be located not only on the junction, but at any point of any road.

N/A

N/A