निकटतम अस्पताल

यहाँ n शहर हैं, जो m द्विदिश सड़कों से जुड़े हुए हैं। हर शहर या तो एक सामान्य शहर हो सकता है या फिर ऐसा शहर जिसमें अस्पताल हो। आपको सड़कों के नेटवर्क के आधार पर प्रत्येक शहर के सबसे पास स्थित अस्पताल तक की दूरी ढूँढ़नी है।

इनपुट

पहली पंक्ति में दो स्पेस द्वारा अलग किए गए पूर्णांक n और m () दिए होते हैं, जो क्रमशः शहरों की संख्या और सड़कों की संख्या को दर्शाते हैं।

दूसरी पंक्ति में n स्पेस से अलग किए गए पूर्णांक (0 या 1) होते हैं, जहाँ शहर i की अस्पताल स्थिति बताता है। यदि का मान 1 है, तो शहर i में अस्पताल है।

अगली m पंक्तियों में से प्रत्येक में तीन स्पेस से अलग किए गए पूर्णांक और (, ) होते हैं, जो शहर और शहर के बीच की द्विदिश सड़क को दर्शाते हैं, जिसकी लंबाई होती है।

यह सुनिश्चित किया गया है कि सभी शहर आपस में जुड़े हुए हैं और कम से कम एक अस्पताल अवश्य है।

आउटपुट

एक ही पंक्ति में n स्पेस से अलग किए गए पूर्णांक निकालें, जहाँ i-वाँ पूर्णांक शहर i से निकटतम अस्पताल की दूरी को दर्शाता है।

उदाहरण