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