Во Финкидонија постојат N градови кои се означени со броевите од 1 до N. Некои од градовите се поврзани со директни двонасочни патишта - притоа, се знае дека за поминување низ кој било од овие патишта потребно е да се плати патарина. Можно е да се стигне од кој било град до кој било друг град или директно (преку еден пат) или индиректно преку повеќе.

Секој студент по информатика во државата Финкидонија добива M купони за попуст на патарините. Секој купон има вредност за која може да ја намали цената на една патарина - доколку цената на патарината е P, а купонот има вредност K, при патување низ таа патарина студентот ќе треба да плати цена (P-K), или да не плати ништо доколку K >= P. Нормално, од кога ќе се искористи еден купон, тој веќе не може да се искористи за патување - на таа или друга патарина. Слично, на една патарина не може да се искористат повеќе купони наеднаш за да се намали цената повеќекратно.

Нека со D(X, Y) ја означиме најмалата цена за патување од градот X до градот Y, која може да се постигне користејќи ги купоните кои ги имаме на располагање.
Со цел анализа на патната мрежа и купонската поддршка, управникот на Финкидонија го интересира колку е збирот на сите D(X, Y), каде (X, Y) го претставува секој неподреден пар од градови. На пример, доколку имаме три градови, се бара збирот D(1, 2) + D(1, 3) + D(2, 3). Напишете програма која го пресметува и печати овој збир.

Да повториме: се интересираме за збирот на цените на сите независни патувања (со други зборови, пресметката на D(1, 2) не влијае на пресметката на D(1, 3) - имено, иако секој купон може да се искористи по најмногу еднаш во едно патување - на пример при пресметката на пат од X=1 до Y=2, сепак понатаму при пресметката на D(1, 3) почнуваме независно од почеток, земајќи ги предвид сите купони).

Влез

Во првиот ред се запишани три цели броеви N, R и M (2 <= N, M <= 20, 1 <= R <= N*N), кои го означуваат бројот на градови, бројот на патишта и бројот на купони.

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

Во последниот ред се запишани M цели броеви Ki (1 <= Ki <= 1 000 000 000) кои ја означуваат вредноста на секој од купоните.

Забелешка:
Во тест случаи кои носат најмалку 14% од поените, ќе важи N = 2.
Во други тест случаи кои носат најмалку 11% од поените, ќе важи N <= 5.
Во други тест случаи кои носат најмалку 12% од поените, ќе важи Pi = 1.

Излез

Отпечатете го бараниот збир.

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

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

Примери

влез
3 2 2
1 2 6
2 3 6
1 3

излез
14

Објаснување: Збирот е D(1, 2) + D(1, 3) + D(2, 3) = 14 = 3 (патарина со цена 6 за патот од 1 до 2, но одземаме 3 со искористен купон) + 8 (патарина 6 - 3 на патот од 1 до 2, и патарина 6 - 1 на патот од 2 до 3) + 3 (патарина со цена 6 за патот од 2 до 3, но одземаме 3 со искористен купон). Забележете дека на патувањето од 1 до 3 поминавме низ две патарини (директен пат од 1 до 2, па директен пат од 2 до 3), и за првата патарина го искористивме вториот купон со вредност 3, а за втората патарина го искористивме првиот купон бидејќи не можеме еден ист купон да го користиме повеќе пати.