Matcom Online Grader

En colaboración con la IOI, Pattaya City será sede de una carrera: la Olimpiada Internacional de Carreras (OIC) 2011. Como anfitriones, tenemos que encontrar el mejor recorrido posible para la carrera.
En el área metropolitana de Pattaya-Chonburi hay N ciudades conectadas por una red de N-1 autopistas. Cada autopista es bidireccional, conecta dos ciudades diferentes, y su longitud es un número entero de kilómetros. Además, hay exactamente un camino posible que conecta cualquier par de ciudades. Es decir, hay exactamente una forma de viajar de una ciudad a otra siguiendo una secuencia de autopistas sin visitar ninguna ciudad dos veces.
La OIC tiene unas normas específicas que requieren que el recorrido sea un camino de exactamente K kilómetros, empezando y finalizando en ciudades diferentes. Obviamente no se puede usar dos veces una carretera (y por lo tanto tampoco una ciudad) a lo largo del recorrido, con el fin de prevenir accidentes. Para minimizar las restricciones de tráfico el recorrido debe estar compuesto por el mínimo número posible de autopistas.

TAREA
Escribe un programa que lea de la entrada estándar los siguientes parámetros: N – el número de ciudades, cada ciudad está numerada de 0 a N-1, K – la distancia del recorrido y La distribución de las autopistas. Tu programa debe escribir el mínimo número de autopistas de un recorrido valido de la carrera de longitud exactamente K. Si no existe tal recorrido tu programa debe escribir -1.

Línea 1 : Dos enteros N y K (1 <= N <= 200000, 1 <= K <= 1000000).
Línea 2...N : Tres enteros por línea Ai, Bi y Ci separados por espacios, indicando que la i-ésima autopista conecta las ciudades Ai y Bi (diferentes) y dicha autopista tiene una longitud de Ci kilómetros (0 <= Ai, Bi < N, 0 <= Ci <= 1000000).

Hint
Caso 1 : La carrera puede empezar en la ciudad 0, ir a la ciudad 1 y acabar en la ciudad 2. Su longitud será exactamente 1 km + 2 km = 3 km, y consiste en dos autopistas. Esta es la mejor ruta posible; por tanto usted debe imprimir 2.
Caso 2 : No existe ninguna ruta válida. En este caso, debe imprimir -1.
Caso 3 : Una ruta posible consiste en 3 autopistas: desde la ciudad 6 a la ciudad 3, pasando por las ciudades 0 y 2. Otra posible ruta empieza en la ciudad 10 y va a la ciudad 6 pasando por la ciudad 8. Ambas rutas tienen una longitud de 12 km exactamente, como se busca. La segunda de ellas es óptima, ya que no existe ninguna ruta válida consistente en una única autopista. Por tanto la solución es 2.