题目描述

译自 POI 2007 Stage 3. Day 0「Railway」

Byteland 的铁路不得不重建并简化。在深度研究后，上级决定了哪些火车站将被移除，哪些将留下。并且决定了要尽可能简化铁路网。但哪些铁路线留下，哪些移除仍待决定。

铁路网由连接火车站的铁路组成。现在已知一个人从任意一个车站出发可以到达任意其他车站（可能经过一些中间站）。铁路双向连接两个车站。每一对车站之间至多有一段铁路。每个路段都有一个维护费用，这个维护费用是一个正整数。留下的铁路按以下方式选择：

• 从任意一个没被移除的车站出发可以到达其他任意没被移除的车站；
• 留下铁路的维护费用要小。如果前一个条件满足，你所留下的铁路花费可以最多是最小花费的两倍大。

除了留下的铁路以外的铁路会被移除。剩下的铁路线可以穿过要被移除的车站。

输入格式

第一行包含两个正整数 $n,m$，表示车站数和铁路数；

接下来 $m$ 行，每行包含三个正整数 $a,b,u$，表示 $a$ 和 $b$ 之间有一条维护费用为 $u$ 的铁路。

最后一行的开头为一个正整数 $p$，表示必须要保留的车站数。

接下来包含 $p$ 个正整数，按递增顺序依次给出必须保留的车站的编号。

输出格式

第一行包含两个正整数 $c,k$，其中 $c$ 表示剩余铁路的费用总和，$k$ 表示剩余铁路的条数。

接下来 $k$ 行，每行包含两个正整数 $a,b$，表示一条铁路的两个端点。

如有多组解，输出任意一组。

样例

8 11
1 2 6
3 1 5
2 3 8
3 4 9
3 5 10
5 4 3
5 6 9
6 4 8
6 8 8
6 7 7
8 7 10
4 2 5 7 8

42 5
2 3
3 5
5 6
6 7
6 8

数据范围与提示

对于全部数据，$2\le n\le 5\times 10^3,1\le m\le 5\times 10^5,1<\le a,b\le n,a\neq b,1\le u\le 10^5,2\le p\le n,p\times m\le 1.5\times 10^7$。