Ամենամոտ հիվանդանոցը

Տրված է n քաղաք, որոնք միացված են m երկկողմանի ճանապարհներով։ Յուրաքանչյուր քաղաք կամ սովորական քաղաք է, կամ քաղաք է, որտեղ կա հիվանդանոց։ Ձեր խնդիրն է պարզել, թե յուրաքանչյուր քաղաքի համար որն է ամենամոտ հիվանդանոցի հեռավորությունը՝ հաշվի առնելով ճանապարհների ցանցը։

Մուտք

Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր n և m ($1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5$), որոնք ցույց են տալիս քաղաքների քանակը և ճանապարհների քանակը, համապատասխանաբար։

Մուտքի երկրորդ տողում տրված են n տարածքով բաժանված թվեր h_1, h_2, ..., h_n (0 կամ 1), որտեղ h_i-ն ցույց է տալիս, թե արդյոք քաղաք i-ում հիվանդանոց կա (եթե h_i = 1, ուրեմն քաղաք i-ում բուժհաստատություն կա)։

Հաջորդ m տողերից յուրաքանչյուրում տրված են երեք ամբողջ թվեր u_i, v_i և w_i ($1 ≤ ui, vi ≤ n$, $1 ≤ wi ≤ 10^9$), որոնք ներկայացնում են երկկողմանի ճանապարհ քաղաքների ui և vi միջև, որի երկարությունը wi է։

Ենթադրվում է, որ բոլոր քաղաքները վերջնականորեն կապակցված են, և առնվազն մեկ քաղաք հաստատ ունի հիվանդանոց։

Ելք

Պետք է տպել մեկ տող, содержащ n տարածքով բաժանված ամբողջ թվեր. i-րդ թիվը պետք է ցույց տա, թե ինչքան է հեռավորությունը ամենամոտ հիվանդանոցից մինչև քաղաք i:

Օրինակներ