DFS Exploration in Weighted Graph

In this problem, you are given a connected, weighted, undirected graph (G) with (n) nodes and (n) edges. Each edge has two weights: an aesthetic value and a length. Ryoku explores the world following a strategy similar to a depth-first traversal. Starting from a chosen vertex (s), at each vertex she moves along the outgoing edge with the highest aesthetic value among those she has not yet used from that endpoint. If no such edge exists, she backtracks along the edge she arrived by (the length of backtracking edges is not counted). The forward edge lengths (the ones chosen based on aesthetic order) are summed to determine the length of the exploration.

For every starting vertex (s=1,2,\ldots,n), compute the total sum of lengths traveled in forward moves following this DFS strategy.

Note: When selecting an edge, if there are multiple edges with the same aesthetic value, you may choose any one of them.

inputFormat

The first line contains an integer (n) representing the number of vertices (and also the number of edges). Each of the following (n) lines contains four integers (u), (v), (a), and (L), where (u) and (v) are the endpoints of an edge, (a) is its aesthetic value, and (L) is its length.

outputFormat

Output a single line with (n) integers. The (i)-th integer represents the total forward travelled length when the exploration starts from vertex (i). Separate adjacent numbers by a space.

sample

3
1 2 5 10
2 3 3 100
3 1 4 20

260 260 260