Background

As a well-known foodie in JSOI, one of JYY’s dreams is to taste delicious food from all over the world. To travel around the world, he naturally needs to keep taking flights. The meals provided on different flights are very different: for example, flights in China provide Chinese food, flights in the UK have milk tea and cakes, flights in Australia have seafood, and flights in Singapore have ice cream...

JYY picked some flights whose meals he especially wants to try. He hopes to make a travel plan with the minimum cost: starting from Nanjing, taking all these flights, and finally returning to Nanjing.

Problem Description

There are $N$ cities in the world that JYY is willing to visit, numbered from $1$ to $N$. JYY selected $K$ flights that he must take. Besides these, there are $M$ flights that JYY has no special preference for; he may take them or not.

We represent a flight with a triple $(x,y,z)$, meaning that this flight connects city $x$ and city $y$, and the ticket cost is $z$. Each flight is round-trip, so after paying $z$, JYY can choose to fly from $x$ to $y$ or from $y$ to $x$.

Nanjing is numbered as $1$. Now JYY plans to start from Nanjing, take all $K$ flights, and finally return to Nanjing. Please help him find the minimum total cost.

Input Format

The first line contains two integers $N$ and $K$.

The next $K$ lines each contain three integers $x,y,z$, describing the flights that must be taken. The testdata guarantees that among these $K$ flights, there are no two different flights operating between the same pair of cities.

Line $K+2$ contains an integer $M$. The next $M$ lines each contain three integers $x,y,z$, describing the flights that may be taken or not.

Output Format

Output one line containing one integer, representing the minimum total cost. The testdata guarantees that there exists at least one travel plan satisfying JYY’s requirements.

6 3
1 2 1000
2 3 1000
4 5 500
2
1 4 300
3 5 300

3100

Hint

Sample Explanation

One feasible optimal plan is $1\rightarrow 2\rightarrow 3\rightarrow 5\rightarrow 4\rightarrow 1$.

The ticket cost is $1000+1000+300+500+300=3100$.

Constraints

For $100\%$ of the testdata, $2\leq N\leq 13,0\leq K\leq 78,2\leq M\leq 200,1\leq x,y\leq N,1\leq z\leq 10^4$。

Translated by ChatGPT 5