Comprando un Boleto
Músicos de una popular banda "Flayer" han anunciado que van a "hacer su salida" con una gira mundial. Por supuesto, también visitarán Berland.
Hay ciudades en Berland. Las personas pueden viajar entre ciudades utilizando rutas de tren bidireccionales; hay exactamente rutas, la i-ésima ruta se puede usar para ir de la ciudad a la ciudad (y de la a la ), y cuesta monedas usar esta ruta.
Cada ciudad será visitada por "Flayer", y el costo de la entrada al concierto en la i-ésima ciudad es de monedas.
Tienes amigos en todas las ciudades de Berland, y ellos, conociendo tus habilidades de programación, te pidieron que calcularas la cantidad mínima posible de monedas que tienen que pagar para visitar el concierto. Para cada ciudad tienes que calcular la cantidad mínima de monedas que una persona de la ciudad tiene que gastar para viajar a alguna ciudad (o posiblemente permanecer en la ciudad ), asistir a un concierto allí y regresar a la ciudad (si \(j ≠ a[i]\)).
Formalmente, para cada entre y uno debe calcular , donde es el número mínimo de monedas que se debe gastar para viajar de la ciudad a la ciudad . Si no hay forma de llegar a la ciudad desde la ciudad , entonces consideramos que es infinitamente grande.
Entrada
La primera línea contiene dos números enteros n y m .
Luego siguen líneas, la i-ésima contiene tres enteros , y \((1 \leq v[i], u[i] \leq n, v[i] ≠ u[i], 1 \le w[i] \leq 10^{12} )\) que denotan la i-ésima ruta del tren. Puede haber mas de una ruta de tren entre dos ciudades.
La siguiente línea contiene n números enteros )~ - el precio para asistir al concierto en la i-ésima ciudad.
Salida
Imprime enteros. i-ésimo de ellos debe ser igual al número mínimo de monedas que una persona de la ciudad tiene que gastar para viajar a alguna ciudad (o posiblemente quedarse en la ciudad ), asistir a un concierto allí y regresar a la ciudad (si \(j ≠ i\)).
Puntuación:
Subtarea 1: , (40 puntos)
Subtarea 2: Sin retricciones adicionales (60 puntos)
Ejemplo de Entrada 1:
4 2
1 2 4
2 3 7
6 20 1 25
Ejemplo de Salida 1:
6 14 1 25
Ejemplo de Entrada 2:
3 3
1 2 1
2 3 1
1 3 1
30 10 20
Ejemplo de Salida 2:
12 10 12
Comments