L’Hôpital le plus proche

Il existe n villes, reliées par m routes bidirectionnelles. Chaque ville peut être une ville ordinaire ou une ville disposant d’un hôpital. Votre mission consiste à déterminer, pour chaque ville, l’hôpital le plus proche en fonction du réseau routier.

Entrée

La première ligne contient deux entiers séparés par un espace, n et m (), qui représentent respectivement le nombre de villes et le nombre de routes.

La deuxième ligne contient n entiers séparés par des espaces (0 ou 1), où indique le statut d’hôpital de la ville i. Si vaut 1, alors la ville i possède un hôpital.

Les m lignes suivantes décrivent chacune une route bidirectionnelle et contiennent trois entiers séparés par des espaces : et (, ), représentant une route entre les villes et de longueur .

On garantit que les villes sont toutes connectées et qu’au moins une ville possède un hôpital.

Sortie

Affichez une unique ligne composée de n entiers séparés par des espaces. Le iᵉ entier doit indiquer la distance entre la ville i et l’hôpital le plus proche.

Exemples