Comprando un Boleto


Submit solution


Points: 100 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Prolog, Python, Swift, VB

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 n ciudades en Berland. Las personas pueden viajar entre ciudades utilizando rutas de tren bidireccionales; hay exactamente m rutas, la i-ésima ruta se puede usar para ir de la ciudad v[i] a la ciudad u[i] (y de la u[i] a la v[i]), y cuesta w[i] 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 a[i] 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 i tienes que calcular la cantidad mínima de monedas que una persona de la ciudad i tiene que gastar para viajar a alguna ciudad j (o posiblemente permanecer en la ciudad i), asistir a un concierto allí y regresar a la ciudad i (si \(j ≠ a[i]\)).

Formalmente, para cada i entre 1 y n uno debe calcular min(2 * d(i, j) + a[j]), donde d (i, j) es el número mínimo de monedas que se debe gastar para viajar de la ciudad i a la ciudad j. Si no hay forma de llegar a la ciudad j desde la ciudad i, entonces consideramos que d (i, j) es infinitamente grande.

Entrada

La primera línea contiene dos números enteros n y m (2 \leq n \leq 2 * 10^5, 1 \leq m \leq 2 * 10^5).

Luego siguen m líneas, la i-ésima contiene tres enteros v[i], u[i] y w[i] \((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 a[1], a[2], ... a[k] (1 \leq a[i] \leq 10^{12} )~ - el precio para asistir al concierto en la i-ésima ciudad.

Salida

Imprime n enteros. i-ésimo de ellos debe ser igual al número mínimo de monedas que una persona de la ciudad i tiene que gastar para viajar a alguna ciudad j (o posiblemente quedarse en la ciudad i), asistir a un concierto allí y regresar a la ciudad i (si \(j ≠ i\)).

Puntuación:

Subtarea 1: 2 \leq N \leq 200, 1\leq M \leq 1000 (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

There are no comments at the moment.