提示: 欢迎访问OurACM平台。
Problem 1963 交通建设

Accept: 32    Submit: 246
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

LL国交通环境相当落后,城市之间没有公路连接,城市里没有飞机场.

作为LL国的交通部长,yayamao致力于改善LL国落后的交通环境.

为了达到这个目的,yayamao启动了新的交通建设计划.

yayamao打算在城市之间修建公路或在城市中建造飞机场.修建一个飞机场需要CA费用.而修建一条长为L的公路需要CB*L的费用.

yayamao希望建设后两两城市可达.对任意的城市A,B,以下任意条件成立则A,B为可达:

1. A和B有公路相连

2. A和B都有飞机场

3. 存在第三个城市C,使得A,B与C都可达

在项目开展一段时间后,yayamao突然发现预算有点紧张,他急于知道完成此项建设计划的最小花费(包含已修建的部分).

已知LL国的交通建设现状,现在你的任务就是确定此项建设计划的最少花费(包含已修建的部分).

Input

输入包含多组数据。

每组数据第一行有四个正整数N(1<=N<=1000),M(1<=M<=10000),CA(1<=CA<=1000),

CB(1<=CB<=1000),N表示LL国城市的数量,M表示可修建的公路的数量,CA表示建造一个机场的费用,CB表示建造单位长度的公路的费用.

接下去M行,第i行为第i条公路,每行有3个数Ai,Bi,Li

(1<=Ai,Bi<=N,Ai!=Bi,1<=L<=1000),

表示可以在城市Ai,Bi之间建一条长度为Li的公路.

接下来一行有一个整数P,(0<=P<=N),表示有P个城市已建好飞机场.接下来有P个不同的整数Pi,表示城市Pi已经建好飞机场.

接下来一行有一个整数Q,(0<=Q<=M),表示有T条公路已经建好.接下来有Q个不同的整数Qi,表示第Qi条公路已经建好.

Output

输出一行,表示此项建设计划的最少花费. (包含已修建的部分).

Sample Input

3 3 100 1 1 2 1 2 3 10 3 1 100 0 0

Sample Output

11

Source

Contest for 2010 lecture I

Submit  Back  Status  Discuss