在 2100 年的臺灣，建中逐漸發展成超級強權，佔領了臺灣的許多領地。建中總共佔領了 $n$ 個領地，可以用 $1$ 到 $n$ 的編號表示。由於建中內部有許多勢力互相爭鬥，所以每個領地各自屬於不同派別，其中，第 $i$ 個領地屬於第 $c_i$ 個派別。領地間有 $n-1$ 條雙向的道路，第 $i$ 條道路連接 $a_i$ 跟 $b_i$ ，長度為 $w_i$，這些道路使得建中的領地兩兩互相連通。

身為一個建中生，當然要請公假到處混。建中設備組推出了新的公假方案，讓你可以請公假去別的領地玩。不幸的是，為了安全著想，若你一開始在第 $x$ 個派別的領地，你也只能去其他第 $x$ 個派別的領地玩（但由於建中有著很優良的高鐵系統，所以旅途的中間可以經過其他派別的領地）。選擇去哪裡玩之後，設備組會用高鐵把你送過去，路程為這兩個領地間的最短距離。

因為你想要混越久越好，所以你想要從所有可以去旅行的領地中，選離你最遠的領地去玩。但由於建中太大了，所以你想寫一個程式，在輸入建中的地圖後，可以對 $1$ 到 $n$ 中的每個領地輸出：如果從第 $i$ 號領地出發，你的旅途距離為多長。

請注意，如果你的領地派別只有佔領你這個領地，那你沒辦法去任何地方，所以你的旅途距離為 $0$。