题目背景

作为 JSOI 的著名吃货，JYY 的理想之一就是吃遍全世界的美食。要走遍全世界当然需要不断的坐飞机了。而不同的航班上所提供的餐食是很不一样的：比如中国的航班会提供中餐，英国的航班有奶茶和蛋糕，澳大利亚的航班有海鲜，新加坡的航班会有冰激凌……

JYY 选出了一些他特别希望品尝餐食的航班，希望制定一个花费最少的旅游计划，能够从南京出发，乘坐所有这些航班并最后回到南京。

题目描述

世界上一共有 $N$ 个 JYY 愿意去的城市，分别从 $1$ 编号到 $N$。JYY 选出了 $K$ 个他一定要乘坐的航班。除此之外，还有 $M$ 个 JYY 没有特别的偏好，可以乘坐也可以不乘坐的航班。

一个航班我们用一个三元组 $(x,y,z)$ 来表示，意义是这趟航班连接城市 $x$ 和 $y$，并且机票费用是 $z$。每个航班都是往返的，所以 JYY 花费 $z$ 的钱，既可以选择从 $x$ 飞往 $y$，也可以选择从 $y$ 飞往 $x$。

南京的编号是 $1$，现在 JYY 打算从南京出发，乘坐所有 K 个航班，并且最后回到南京，请你帮他求出最小的花费。

输入格式

输入数据的第一行包含两个整数 $N$ 和 $K$。

接下来 $K$ 行，每行三个整数 $x,y,z$ 描述必须乘坐的航班的信息，数据保证在这 $K$ 个航班中，不会有两个不同的航班在同一对城市之间执飞。

第 $K+2$ 行包含一个整数 $M$，接下来 $M$ 行，每行三个整数 $x,y,z$ 描述可以乘坐也可以不乘坐的航班信息。

输出格式

输出一行一个整数，表示最少的花费。数据保证一定存在满足 JYY 要求的旅行方案。

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

3100

提示

样例解释

一个可行的最佳方案为 $1\rightarrow 2\rightarrow 3\rightarrow 5\rightarrow 4\rightarrow 1$。

机票所需的费用为 $1000+1000+300+500+300=3100$。

数据范围

对于 $100\%$ 的数据，$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$。