Comet OJ

C1268 [JSOI2013]吃货jyy

内存限制：256 MB 时间限制：1000 ms

题目描述

【故事背景】

作为 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$ 描述可以乘坐也可以不乘坐的航班信息。

$2 \le N \le 13，0 \le K \le 78，2 \le M \le 200，1 \le x,y \le N，1 \le z \le 10^4$

输出

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

样例

样例输入 1

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

样例输出 1

3100

提示

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

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