Descuento único
Alex vive en la ciudad
1 y desea llegar a la ciudad n. Quiere encontrar la ruta de vuelo con el precio más bajo, tomando en cuenta que dispone de un cupón de descuento. Dicho cupón se puede usar solo una vez para reducir a la mitad el precio de un vuelo durante el recorrido. Cuando utiliza el cupón de descuento en un vuelo que cuesta x, el precio pasa a ser .
Encuentra el precio de la ruta más económica desde la ciudad 1 hasta la ciudad n.Entrada
La primera línea contiene dos enteros separados por espacio,
n y m (), que representan la cantidad de ciudades y la cantidad de vuelos, respectivamente.Las siguientes
m líneas describen los vuelos. Cada línea contiene tres enteros separados por espacio: a, b y (), que indican un vuelo bidireccional de la ciudad a a la ciudad b con un precio de .Salida
Imprime un solo entero, que representa el precio de la ruta más económica desde la ciudad
1 hasta la ciudad n.Ejemplos
Entrada | Salida |
6 6
1 2 7
2 3 5
3 6 4
1 4 8
4 5 10
5 6 9 | 12 |
Constraints
Time limit: 5.4 seconds
Memory limit: 512 MB
Output limit: 1 MB