## Necessary Travels

Time Limit: 1 sec
Memory Limit: 756 MB
Attempts: 57
Accuracy: 0.00%
Author: Shubham Garg

The Avengers love trees so Thanos decides to give them the Infinity Gauntlet if they solve this problem :

Given a tree with N nodes where each edge has a cost for traversal in a given direction such that if there is an edge between u and v then there is cost corresponding to traversal from u to v and v to u. The root of the tree is the vertex x. Now some of the directed edges are marked that means you have to traverse each of those edges at least once. Output the minimum possible value of cost of the path starting from root and ending somewhere in the tree and satisfying the conditions for traversal.

Input format :

First line contains an integer t , the number of test cases.

First line of each test case contains two integers N and x .

Next N-1 lines contain 5 integers **i**, **j**, **w1**, **w2** and **p** ;

where i and j are nodes, w1 is the cost of edge from i to j, w2 is the cost of edge from j to i and p tells which of these two edges is marked or not.

p=0 means no edge is marked.

p=1 means only edge i to j is marked.

p=2 means only edge j to i is marked.

p=3 means both the edges are marked.

Output format :

Output one line for each test case containing the minimum cost for the traversal.

Constraints :

1 <= t <= 5

1 <= N <= 1e5

1 <= w1,w2 <= 1e9

0 <= p <= 3

1 <= i,j <= N

i is not equal to j.

Sum of N over all test cases <= 1e5

Sample Input :

1

6 1

1 2 5 15 2

2 4 17 2 0

1 3 4 23 1

3 6 8 10 2

3 5 19 19 0

Sample Output :

42

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED

4 years ago

cpp14

0.07 sec

64 KB

4 years ago

cpp14

0.07 sec

64 KB

4 years ago

cpp14

0.07 sec

64 KB