Alex y su país
En el país donde vive Alex hay n ciudades numeradas de a . La ciudad es la capital. También hay carreteras bidireccionales conectando las ciudades. Alex sabe que el tamaño de la i-ésima carretera es y que esta conecta a las ciudades y . Además en este país hay rutas de trenes (bidireccionales), la i-ésima ruta conecta a la capital con la ciudad y el tamaño de esta ruta es .
Alex quiere cerrar la mayor cantidad de rutas de trenes de tal forma que el tamaño del camino mínimo desde la capital hacia cualquier otra ciudad no cambie.
Note que al cerrar una ruta de tren esta no se puede seguir utilizando.
Formato de entrada:
La primera línea contiene tres enteros .
Las siguientes líneas contienen tres enteros \(ui,vi,xi (1<=ui,vi<=n;ui≠vi;1<=xi<=10^9)\).
Las siguientes líneas contienen dos enteros .
Se garantiza que se puede ir desde la capital hacia cualquier otra ciudad. Note que pueden haber múltiples carreteras entre un mismo par de ciudades, también note que pueden haber múltiples rutas de trenes desde la capital hacia una ciudad.
Formato de salida:
En una única línea imprima un entero representando la máxima cantidad de rutas de trenes que Alex puede cerrar.
Entrada #1
5 5 3
1 2 1
2 3 2
1 3 3
3 4 4
1 5 5
3 5
4 5
5 5
Salida #1
2
Entrada #2
2 2 3
1 2 2
2 1 3
2 1
2 2
2 3
Salida #2
2
Comments