L'Ospedale Più Vicino

Ci sono n città collegate da m strade bidirezionali. Ogni città può essere una città normale oppure una città con un ospedale. Il tuo compito è determinare, per ogni città, la distanza dall’ospedale più vicino sulla base della rete stradale.

Input

La prima riga contiene due interi separati da spazio, n e m (), che rappresentano rispettivamente il numero di città e il numero di strade.

La seconda riga contiene n numeri interi (0 o 1), dove indica se la città i ha un ospedale (1) oppure no (0).

Le successive m righe contengono ognuna tre interi separati da spazio, e (), che descrivono una strada bidirezionale tra le città e con lunghezza .

Si garantisce che tutte le città siano collegate e che esista almeno un ospedale.

Output

Stampa un’unica riga contenente n numeri interi separati da spazio, dove il valore in posizione i rappresenta la distanza dall’ospedale più vicino alla città i.

Examples