Чланови Комисије су врло заузети људи и увек се погоди да највише обавеза (које немају везе са СИО-ом) имају непосредно пред СИО. Нажалост, неко мора и да смишља задатке и прави тест примере па се увек уочи СИО-а организује популарна трка задужења.

У комисији има \(k\) чланова и сви живе у једном граду који има \(n\) раскрсница нумерисаних бројевима од \(1\) до \(n\) и \(m\) двосмерних улица које повезују неке од раскрсница. За сваког члана комисије је познато на којој раскрсници живи и за сваку улицу је позната њена дужина у метрима. Сваке године се одабере кружна стаза – низ од неколико (бар 3) различитих раскрсница \(x_1, x_2, \ldots, x_l\) при чему између сваке две узастопне раскрнице на кружној стази постоји нека улица (тј. постоје улице између раскрсница \(x_1\) и \(x_2\), \(x_2\) и \(x_3\), \(\ldots\), \(x_l\) и \(x_1\)). Улице кружне стазе се покривају посебним материјалом погодним за трчање – када неко трчи њима, он прелази \(1\) метар за \(a\) секунди док на осталим улицама прелази \(1\) метар за \(b\) секунди (дакле, сви чланови комисије трче истом брзином). Сваки члан комисије мора трчати од своје раскрснице до неке раскрснице на кружној стази (по избору) а затим оптрчати тачно један круг кружне стазе. Ко први заврши трку, иде својим измишљеним обавезама а остали морају да праве тест примере.

Испоставља се да чланови Комисије због својих обавеза нису имали времена да тренирају па им је много битније да победник буде одлучен што пре (јер тада остали могу прекинути ту напорну активност) него да победе у трци. Зато планирају да ургирају код градских власти да се ове године изабере таква кружна стаза за коју важи да је време потребно победнику да заврши трку – најмање могуће. Помозите члановима Комисије да одаберу такву кружну стазу како би стигли да направе тест примере за овај задатак.

Опис улаза

У првом реду стандардног улаза налазе се пет природних бројева \(n\), \(m\), \(k\), \(a\) и \(b\) који, редом, представљају податке из текста задатка. У наредном реду налази се \(k\) природних бројева \(r_i\) – редни бројеви раскрсница на којима живе чланови комисије. У наредних \(m\) редова налазе се по три броја \(x_i\), \(y_i\) и \(z_i\) који означавају да између раскрснице број \(x_i\) и раскрснице број \(y_i\) постоји улица дужине \(z_i\) метара.

Опис излаза

У првом и једином реду стандардног излаза исписати један цео број - најмањи време (у секундама) потребно да победник заврши трку при оптималном избору кружне стазе. Увек ће постојати бар једно решење.

Пример 1

Улаз

8 12 3 1 2
4 2 7
1 5 1
7 5 6
2 7 1
7 3 11
8 1 7
2 3 20
4 6 2
1 6 2
2 4 10
8 6 8
7 8 15
5 8 5

Излаз

20

Пример 2

Улаз

3 3 1 10 5
2
1 2 11
2 3 12
3 1 13

Излаз

360

Објашњење примера

У првом примеру имамо укупно 8 раскрсница и 3 члана Комисије који живе на раскрсницама 4, 2 и 7. Оптимално је одабрати кружну стазу 5-8-6-1-5. Тада при оптималном трчању, члан Комисије који живи на раскрсници број 4 трчи до стазе улицом 4-6 дужине 2 а затим трчи стазом (улицама 6-8, 8-5, 5-1 и 1-6) док не обиђе целу стазу, тј. док се не врати на раскрсницу 6. Укупно му је требало \(2 \cdot b + 8 \cdot a + 5 \cdot a + 1 \cdot a + 2 \cdot a\) = 20 секунди. Чланови комисије са раскрсница 2 и 7 би, редом, завршили трку после 30 и 28 секунди; дакле, за овај избор кружне стазе, члан са раскрснице 4 је победник и трка се прекида после 20 секунди. Не постоји избор кружне стазе тако да победник буде одлучен за мање од 20 секунди.

Ограничења и подзадаци

• \(3 \leq n \leq 500\)
• \(n \leq m \leq n(n-1)/2\)
• \(1 \leq k \leq n\)
• \(0 \leq a, b \leq 10^6\)
• \(1 \leq r_i \leq n\), \(r_i \neq r_j\) за \(i \neq j\)
• \(1 \leq x_i, y_i \leq n\), \(x_i \neq y_i\), \(1 \leq z_i \leq 10^9\)
• Између сваке две раскрснице постоји највише једна улица.
• Могуће је доћи од било које раскрснице до било које друге раскрснице користећи дате улице.

Постоји \(6\) подзадатака, у којима додатно важи:

• Подзадатак 1 [8 поенa]: \(n \leq 10\).
• Подзадатак 2 [15 поена]: \(n \leq 80\).
• Подзадатак 3 [18 поена]: \(a = 0\).
• Подзадатак 4 [20 поена]: \(b = 0\).
• Подзадатак 5 [16 поена]: \(k = 1\).
• Подзадатак 6 [23 поена]: Нема додатних ограничења.