9290 - 小李的探索计划

小李对自己所处的世界充满了好奇,他想尽可能能多地探索世界。
这一天,小李得到了一张这个世界的地图,他十分高兴。然而,小李并不知道自己所处的位置到底在哪里,她想要知道如何才能尽可能多的探索这个世界。
假如,小李所处的世界可以抽象成一个有n个点,n 条边的带权无向连通图G。每条边有美观度和长度。小李会使用这样一个策略探索世界:在每个点寻找一个端点她未走过的边中美观度最高的走,如果没有边走,就沿着她前往这个点的边返回,类似于图的深度优先遍历。 探索的一个方案的长度是这个方案所经过的所有边长度的和(返回时经过的长度不用计算)。
他想知道,对于每一个起点 s=1,2,⋯,n,他需要走过的长度是多少?

输入

输入包含n+1 行,其中第一行包含一个整数n。
接下来n行每行包含四个整数u,v,w,p,描述了一条连接u和v,长度为w,美观度为p的无向边。

输出

输出包含n行,每行一个整数,第i行为s=i时的答案。

样例

输入

5
4 1 2 1
1 2 3 2
3 1 1 4
3 5 2 5
2 3 2 3

输出

7
7
8
7
8
时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题