SP28461 TAP2016G - Efficient managing

Nlogonia 的铁路网络由 **N** 个车站组成，每个车站都位于王国的不同城市。某些车站之间通过铁路直接相连，并且双向通车。经过多年的优化，「城市完美连接研究所」（ICPC）确保了这个铁路网络的高效性，现在任意两个城市之间都只有一条唯一的铁路路径。旅客在不同车站之间旅行时，可能需要多次换乘，但他们安心地知道，不用费心思去选择路线，因为路只有一条。 每一趟列车都有它特定的票价，如果旅客在旅行途中需要多次乘坐列车，他就得提前买好所有的票。Nlogonia 的货币很特别，拥有所有非负整数次幂的 2 的面值。换句话说，这里有面值为 **2 $^0$ = 1**、**2 $^1$ = 2**、**2 $^2$ = 4** 等等的纸币。为了充分运用这种货币效率，Nlogonia 的居民总会用最少数量的纸币来支付车票。 为了加快购票流程，「计钱机构」（ACM）推出了一种优惠政策：乘客可以提前支付整个旅程的票款。这样做的时候，他需要递交所有在旅途中使用的纸币，而 ACM 只会收下每种面额中乘客提供的奇数张。举个例子，如果一名旅客需要购买三张票，价格分别是 **3**、**7** 和 **10**，那么他要提交的纸币为：第一张票需要面额 **1** 和 **2** 的纸币各一张，第二张票需要面额 **1**、**2** 和 **4** 的纸币各一张，第三张票需要面额 **2** 和 **8** 的纸币各一张。ACM 会收下面额 **2** 的纸币中的一张，还有 **4** 和 **8** 各一张，剩余的则返还给旅客。 ACM 的管理委员会担心这样的优惠政策会导致财政负责过重，事实也确实如此，因为甚至有可能出现免费旅行的情况（比如任何往返旅行因为票数相等而免费）。您的任务是帮助评估问题的严重程度，因此 ACM 指定你计算从 Nlogonia 每个车站出发的乘客可能需要支付的最大金额。

输入文件包含若干个测试用例。第一行包含一个整数 **N**，表示 Nlogonia 中车站的数量（**2 ≤ N ≤ 10 $^5$**），车站编号从 **1** 到 **N**。接下来的 **N-1** 行每行包含三个整数 **A**、**B** 和 **C**，表示车站 **A** 和 **B** 之间有一条直接铁路，票价为 **C**（**1 ≤ A, B ≤ N**，**1 ≤ C ≤ 10 $^9$**，且 **A ≠ B**）。铁路网络保证任意两个不同的车站之间存在唯一的线路。

对于每个测试用例，输出 **N** 行，每行包含一个整数。第 **i** 行的整数表示从编号为 **i** 的车站出发的乘客在使用所述优惠政策后可能要支付的最高票价。 **本翻译由 AI 自动生成**