Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Cheap Tourist

By zobayer · Limits 1s, 512 MB

The country of Byteland is divided into N provinces numbered from 1 to N. The provinces are connected via N-1 bidirectional roads in a way that it is possible to reach each province from every other province by using one or more of these roads. Candyman is a cheap tourist who wants to visit every province starting from 1 to N in order. Therefore, he starts from province 1, travels to province 2, from province 2, he travels to province 3, so on and so forth until he reaches province N where his journey ends.

In order to travel between two provinces, he needs to purchase a traveler’s pass ticket. There are two types of tickets for each road: single-pass, and multiple-pass. A single-pass ticket expires each time Candyman uses its corresponding road and he needs to purchase it again if he wishes to use that particular road in the future. A multiple-pass ticket, however, does not expire and can be used as many times as necessary for a particular road.

As you can already imagine, both types of passes have two different costs associated with them. For each road ‘i’, a single-pass ticket costs Si bitcoins, and a multiple-pass ticket costs Mi bitcoins. For this problem, you have to help Candyman to figure out the minimum total cost for finishing his travel routes.

Input

The first line of input contains T (1 <= T <= 10), the number of test cases.

The first line of each test contains an integer N (2 <= N <= 200000), the number of provinces in Byteland. Each of the following N-1 lines contains four integers, U, V, Si, Mi, denoting, there’s a bidirectional road between provinces U and V, and the bitcoin costs of single-pass and multiple-pass tickets for this road respectively. Here, 1 <= U, V <= N and 1 <= Si <= Mi <= 100000.

Output

For each test case, print a line containing the minimum bitcoin amount Candyman needs to finish his journey.

Sample

InputOutput
3
4
1 2 3 5
1 3 2 4
2 4 1 3
4
1 4 5 5
3 4 4 7
2 4 2 6
5
1 2 2 3
1 3 2 3
1 4 2 3
1 5 2 3
10
16
11

Large dataset, please use faster IO operations.

    Discussion

    Statistics


    33% Solution Ratio

    IshtiaqEarliest, 3w ago

    IshtiaqFastest, 0.4s

    IshtiaqLightest, 51 MB

    IshtiaqShortest, 3427B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.