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