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

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

Влез

Во првата линија се запишани три цели броја N (1 <= N <= 40 000), K (1 <= К <= 15) и R (1 <= R <= 50 000), кои го означуваат вкупниот број на градови во државата, бројот на градови кои што треба да се посетат, како и бројот на патишта, соодветно. Можете да претпоставите дека патната инфраструктура е таква што постои можност да се стигне од кој било град, во кој било друг.

Во втората линија се запишани K цели броеви Ci (1<= Ci < N), кои ги означуваат градовите кои треба да се посетат. Градовите се нумерирани со броевите од 0 до N-1. Тимот кој ќе ги одржува презентациите секогаш тргнува од градот означен со број 0.

Во секоја од следните R линии се запишани по три цели броја Ai, Bi и Di (0 <= Ai, Bi < N-1, 1 <= Di <= 10 000), кои означуваат дека постои двонасочен пат помеѓу градовите Ai и Bi, со должина Di.

Забелешка: Во тест случаи кои ќе носат најмалку 40% од поените, ќе важи (1 <= K <= 5).

Излез

Отпечатете ја бараната должина на најкраткиот пат.

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

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

Примери

влез
6 4 7
2 3 4 1
0 3 1
0 1 4
3 2 3
1 5 1
3 4 10
0 2 19
2 1 2

излез
30

Објаснување за првиот пример: Треба да се посетат градовите 1, 2, 3 и 4. Најкраткиот пат е 0->3->4->3->2->1->0, со вкупна должина 30.