Скоро секоја година, во Македонија се одржуваат избори на кои учествуваат разни политички партии. Притоа, на некои избори се одлучува кој ќе биде претседател на државата, на други кои пратеници ќе бидат дел од Собранието на Република Македонија, додека на трети се одлучува за градоначалници и советници на општините во државата.

За да ги мотивираат гласачите да излезат во што поголем број и да гласаат за "вистинскиот" избор, партиите организираат разни предизборни кампањи. Кога се организираат ваквите кампањи, потребно е да се формираат изборни штабови во одредени населени места од државата. За таа цел, мора лидерот со неговиот тим (сите во едно комби) да отпатува до секое од тие места. Притоа, лидерот тргнува од местото во кое е седиштето на партијата и е спремен да патува од место во место дури не се заврши работата.

Државата има вкупно N населени места, кои се меѓусебно поврзани со R двонасочни патишта. Дополнително, за секој од тие R патишта, знаеме колку пари треба да се платат за патарина (за комби) кога се поминува низ тој пат. Тимот го започнува формирањето штабови од населеното место означено со бројот 0. Ваша задача е, за дадена листа од M населени места во кои одредена партија сака да формира изборни штабови, да пресметате колку најмалку средства треба да исплати таа партија за патарина за да ги формира штабовите?

Притоа, доколку една партија веќе има формирано изборни штабови во две населени места X и Y, нивен тим не мора да плаќа патарини кога патува од Х до Y бидејќи има опција на патарините да приложи покана добиена по факс од штабот од Y до штабот во Х, дека се повикани на партиски состанок.

На пример, на првата слика (лево) е претставено едно патување од населено место означено со бројот 1, до населено место означено со бројот 5. Населените места во кои партијата веќе има формирано изборни штабови се означени со ѕвездичка. Забележете дека, на патувањето, тимот ќе плати за патарина од местото 1 до местото 3, па нема да плати за патарина помеѓу населените места 3 и 4 (бидејќи, во тие населени места, партијата има формирано изборни штабови и тимот може да добие покана за патување од штабот во 4 која ќе пристигне во штабот во 3), па ќе плати за патарина помеѓу населените места 4 и 5.

На втората слика (десно) е претставено патување помеѓу населените места 1 и 3. Тука, партијата ќе мора да плати на двете патарини (помеѓу 1 и 0, и помеѓу 0 и 3), бидејќи патувањето не се одвива помеѓу две населени места во кои партијата има формирано свои изборни штабови.

Забрането е да се искористи поволноста за неплаќање на патарина помеѓу две населени места X и Y во кои веќе има формирано изборни штабови, за да се формира изборен штаб во некое населено место кое се наоѓа на пат од X до Y. На пример, за првата слика (лево), не смее да се искористи поволноста за бесплатно патување помеѓу 3 и 4 за да се формира штаб во 2.

Според горното објаснување, можно е за една иста патарина еднаш да треба да се плати (доколку тимот не е на пат помеѓу две места во кои партијата веќе има формирано изборни штабови), додека другпат не.

Влез

Во првиот ред се запишани два цели броја N (2 ≤ N ≤ 100000) и R (1 ≤ R ≤ 100000), кои го означуваат бројот на населени места и бројот на патишта, соодветно.

Во секој од следните R редови се запишани по три цели броја Xi, Yi (0 ≤ Xi < Yi < N) и Pi (1 ≤ Pi ≤ 100000000), кои означуваат дека постои двонасочен пат кој ги поврзува Xi и Yi, и кога се патува помеѓу тие две места (во која било насока) потребно е да се плати вредност Pi за патарина. Ниту еден пар населени места нема да се појави повеќе од еднаш. Секогаш ќе постои начин да се стигне од кое било населено место до кое било друго.

Во следниот ред е запишан еден цел број M (1 ≤ M ≤ N), кој го означува бројот на изборни штабови кои треба да се формираат. Во секој од следните M редови е запишан по еден цел број Si (0 ≤ Si < N), кои ги означуваат населените места во кои треба да се формираат изборни штабови. Секое населено место ќе се појави по најмногу еднаш.

Излез

Отпечатете ја бараната минимална вредност која треба да се плати за патарина.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
3 3
0 1 3
1 2 2
0 2 10
1
2

излез
5

влез
4 3
0 1 1
0 2 1
1 3 1
4
0
1
2
3

излез
3

Објаснување за вториот пример: Се формира штаб во 0, па се оди до 2 (за цена 1), се формира штаб таму, па се враќаме од 2 до 0 (безпари, бидејќи веќе имаме штабови во 0 и 2), па се оди до 1 (за цена 1), се формира штаб таму, па се оди од 1 до 3 (за цена 1) и се формира штаб во 3.