Sin Heno
Las vacas se han quedado sin heno, un suceso horrible que debe ser remediado inmediatamente. Bessie quiere recorrer algunas de las otras granjas (numeradas ) para investigar su situación de heno. Ella recorrerá algunos de todos los caminos de doble vía cuya longitud no excede que conectan las granjas. Algunas granjas pueden estar conectadas múltiplemente con caminos de diferentes longitudes.
Bessie está tratando de decidir el tamaño de la cantimplora que ella necesitará. Ella sabe que necesita una onza de agua por cada unidad de distancia de un camino. Dado que ella puede obtener más agua en cada granja, ella únicamente está preocupada por la longitud del camino más largo. Por supuesto, ella planea su ruta entre granjas de tal manera que ella minimice la cantidad de agua que ella debe cargar.
Ayude a que Bessie sepa la cantidad más grande de agua que ella tendrá que cargar: ¿cuál es la longitud del camino más largo que ella tendrá que recorrer entre cualesquiera dos granjas, presumiendo que ella elija rutas que minimicen ese número?
Entrada
• Línea 1: Dos enteros separados por espacio, y .
• Líneas 2…1+M: La línea contiene tres enteros separados por espacios, , , y , describiendo un camino de a de longitud .
Salida
• Línea 1: Un solo entero que es la longitud del camino más largo que necesita ser recorrido.
Ejemplo de Entrada
3 3
1 2 23
2 3 1000
1 3 43
Ejemplo de Salida
43
Explicación
Con el propósito de llegar a la granja , Bessie viaja por un camino de longitud . Para llegar a la granja , Bessie viaja por un camino de longitud . Con una capacidad de , ella puede viajar a lo largo de estos caminos dado que ella recarga su cantimplora a capacidad máxima antes de comenzar un nuevo camino.
Comments