Das nächste Krankenhaus

Es gibt n Städte, die durch m bidirektionale Straßen verbunden sind. Jede Stadt kann entweder eine normale Stadt oder eine Stadt mit einem Krankenhaus sein. Ihre Aufgabe besteht darin, für jede Stadt anhand des Straßennetzes das nächstgelegene Krankenhaus zu ermitteln.

Eingabe

Die erste Zeile enthält zwei durch Leerzeichen getrennte ganze Zahlen, n und m (). Sie geben die Anzahl der Städte bzw. die Anzahl der Straßen an.

In der zweiten Zeile stehen n durch Leerzeichen getrennte ganze Zahlen (0 oder 1). Dabei bedeutet , dass Stadt i ein Krankenhaus hat, wenn der Wert gleich 1 ist.

Die nächsten m Zeilen enthalten jeweils drei ganze Zahlen und (, ). Diese beschreiben eine bidirektionale Straße zwischen den Städten und mit der Länge .

Es ist garantiert, dass alle Städte im Straßennetz miteinander verbunden sind und mindestens eine Stadt ein Krankenhaus besitzt.

Ausgabe

Geben Sie eine einzelne Zeile mit n durch Leerzeichen getrennten ganzen Zahlen aus. Die i-te Zahl entspricht der Entfernung vom nächstgelegenen Krankenhaus zur Stadt i.

Beispiele