吃货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$ 描述可以乘坐也可以不乘坐的航班信息。 其中，$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$。。 ### 输出描述 输出一行一个整数，表示最少的花费。数据保证一定存在满足 JYY 要求的旅行方案。 ### 输入输出样例 #### 示例 1 >输入 ``` txt 6 3 1 2 1000 2 3 1000 4 5 500 2 1 4 300 3 5 300 ``` >输出 ``` txt 3100 ```