El hospital más cercano

Existen n ciudades, conectadas por m carreteras bidireccionales. Cada ciudad puede ser una ciudad común o bien una ciudad que cuente con hospital. Tu tarea consiste en determinar, para cada ciudad, la distancia al hospital más cercano basándote en la red de carreteras.

Entrada

La primera línea contiene dos enteros separados por un espacio, n y m (), que indican la cantidad de ciudades y de carreteras, respectivamente.

La segunda línea contiene n enteros separados por espacios, (0 o 1), donde indica el estado de hospital de la ciudad i. Si es 1, significa que la ciudad i tiene un hospital.

A continuación, se proporcionan m líneas, cada una con tres enteros separados por espacios, y (), que describen una carretera bidireccional entre las ciudades y , con longitud .

Se garantiza que todas las ciudades están conectadas y que existe al menos un hospital.

Salida

Muestra en una sola línea n enteros separados por espacios, donde el i-ésimo entero representa la distancia desde la ciudad i hasta el hospital más cercano.

Ejemplos