最寄りの病院

n 個の都市があり、m 本の双方向道路でつながっています。都市はそれぞれ、ふつうの都市か病院を持つ都市のいずれかです。あなたのタスクは、道路網をもとにして、各都市にとって最も近い病院までの距離を求めることです。

入力

最初の行には、2 つの整数 n と m (スペース区切り) が与えられます ()。これらは、それぞれ都市の数と道路の数を表します。

2 行目には、n 個のスペース区切り整数 h_1, h_2, ..., h_n (0 または 1) が与えられます。ここで h_i は都市 i の病院ステータスを表しており、h_i が 1 の場合、その都市には病院があります。

次の m 行には、それぞれ 3 つのスペース区切り整数 u_i, v_i と w_i () が与えられます。これは、都市 u_i と都市 v_i の間に、長さ w_i の双方向道路があることを示しています。

都市同士が連結で、病院が少なくとも 1 つは存在することが保証されています。

出力

1 行に n 個の整数をスペース区切りで出力してください。ここで、i 番目の整数は都市 i から最も近い病院までの距離を表しています。

例