Mandatory Flight Itinerary

There are \(N\) cities numbered from \(1\) to \(N\) that JYY is willing to visit. JYY has selected \(K\) mandatory flights that he must take, and there are also \(M\) optional flights that he may take if needed. Each flight is represented by a triple \((x, y, z)\) meaning that there is a bidirectional flight between cities \(x\) and \(y\) with a ticket cost of \(z\). JYY starts his journey from Nanjing (city \(1\)), must take all the \(K\) mandatory flights (in any order and direction) exactly once, and finally return to city \(1\). Between mandatory flights, he may take any extra flights (mandatory or optional) any number of times to travel between cities. Your task is to calculate the minimum total cost of such an itinerary. If it is impossible to complete the itinerary, output \(-1\).

inputFormat

The first line contains three integers \(N\), \(K\), and \(M\) separated by spaces.

The next \(K\) lines each contain three integers \(x\), \(y\), \(z\) describing a mandatory flight.

The following \(M\) lines each contain three integers \(x\), \(y\), \(z\) describing an optional flight.

outputFormat

Output a single integer representing the minimum total cost for JYY to start from city \(1\), take all mandatory flights (in some order and chosen directions), and return to city \(1\). If no such itinerary exists, output \(-1\).

sample

3 1 2
1 2 10
2 3 5
1 3 15

20