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

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

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