Envíos de Paquetes
El Granjero Juan debe llevar un paquete al Granjero Dan, y está preparando su viaje. Para mantener la paz, él le da un regalo sabroso a cada vaca con la que él se encuentra en su camino, y por supuesto, a GJ le gusta ahorrar, por lo tanto a él le gustaría encontrarse con tan pocas vacas como sea posible.
Considere el siguiente mapa:
[2]--
/ | \
/1 | \ 6
/ | \
[1] 0| --[3]
\ | / \2
4\ | /4 [6]
\ | / /1
[4]-----[5]
3
GJ ha dibujado un mapa de establos, conectados por caminos bi-direccionales de vacas, cada uno con vacas dentro de cada uno. Un camino de vacas conecta dos establos distintos, y . Dos establos pueden estar conectados directamente por más de un camino. El está actualmente ubicado en el establo 1, y el Granjero Dan está ubicado en el establo N.
El mejor camino que puede tomar el Granjero Juan es ir de , porque le costará regalos.
Entrada
- Línea 1: Dos enteros separados por espacio: y .
- Líneas 2..: Tres enteros separados por espacios: y .
Salida
- Línea 1: El mínimo número de regalos que GJ debe llevar
Ejemplo de Entrada y Salida
Entrada
6 8
4 5 3
2 4 0
4 1 4
2 1 1
5 6 1
3 6 2
3 2 6
3 4 4
Salida
5
Comments