[JSOI2013] 吃货 JYY
题目背景
作为 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 要求的旅行方案。
输入输出样例
输入样例 #1
6 3
1 2 1000
2 3 1000
4 5 500
2
1 4 300
3 5 300
输出样例 #1
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$。