Во една сиромашна држава (со, можеби, најголема невработеност во светот) луѓето живеат во N градови, меѓусебно поврзани со патишта. Притоа, патната инфраструктура во државата се гради според следниот закон: Секој град во даден момент добива пари за да изгради точно еден пат - поврзување со друг град (по нивен избор). Од почетокот на спроведување на законот до денес некои градови ја добиле можноста за градење еднаш, а некои се уште ја немаат добиено. Најверојатно, новата влада и ќе го укине законот, па патната структура ќе остане таква каква што е уште долго време.

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

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

Пресметајте го ова растојание (минимизирајте го најголемото растојание од град без факултет до град со факултет), ако на вас е дадена одговорноста да испланирате во кои градови треба да се изградат новите К факултети.

Влез

Во првиот ред се запишани три цели броја: N (2 <= N <= 60), кој го означува бројот на градови, M (0 <= M < N) – кој го означува бројот на градови во кои веќе има факултети, и K (1 <= K <= N-M) – кој го означува бројот на нови факултети – кои допрва треба да се изградат.

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

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

Излез

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

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

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

Примери

влез
4 2 1
3 4
2
2 3 83
1 2 71

излез
71

влез
4 0 2

4
1 2 3
2 1 10
4 3 5
3 1 7

излез
5

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

излез
0

Објаснување за првиот пример: Државата има 4 градови и 2 града со факултети (градот 3 и градот 4). Може, на пример, да се изгради новиот факултет во градот 2. Тогаш, бараното растојание ќе биде 71.
Забележете дека, поради начинот на кој што се градени патиштата, можно е да постојат градови кои, гледајќи ја патната инфраструктура, се недостапни еден за друг (не може да се најде низа од патишта, така што ќе се стигне од едниот до другиот град).

Објаснување за вториот пример: Државата има 4 градови, но нема ниту еден град со факултет. Може, на пример, да се изградат двата (К=2) нови факултети во градовите 1 и 3. Тогаш, бараното растојание ќе биде 5.