Məmurlar və yollar

Şəhər Flovildə $T$ məmurun seçkiləri keçirilir. Şəhər $N$ zirvə və $M$ kənardan ibarət olan əlaqəli istiqamətsiz qrafla təsvir olunur. Hər bir kənar üç ədəd ilə verilir: $u_i$, $v_i$, $le{n}_i$ (burada $u_i$ və $v_i$ zirvələr arasında kənardır) və $le{n}_i$ kənarın uzunluğunu göstərir.

Hər məmura yaşayış yeri təqdim olunur. Nömrəsi $t$ olan məmur qrafın $h_t$ nömrəli zirvəsində yaşayır. Şəhərdə məmurların işləri üçün $T$ boş ofis var. Nömrəsi $t$ olan məmur qrafın $w_t$ nömrəli zirvəsində ofis seçərsə, hər gün $h_t$ zirvəsindən $w_t$ zirvəsinə ən qısa yolla avtomobillə gedəcək. Məmur mövcud olan bütün ən qısa yollar arasından marşrutu belə seçir: marşrutun zirvə nömrələrini tərsinə düzərək (yəni iş yerindən evə doğru) "leksikoqrafik olaraq ən kiçik" yolu seçir.

Məsələn, əgər 0 zirvəsindən 5 zirvəsinə 2 ən qısa yol varsa: 0→1→2→4→5 və 0→3→5, məmur 0→3→5 yolunu seçəcək. Çünki tərsinə (iş yerindən evə doğru): 5→4→2→1→0 və 5→3→0. "Leksikoqrafik olaraq ən kiçik" yol isə 5→3→0-dır.

Məmurun marşrutu boyunca yerləşən bütün yollar (qrafın kənarları) həmişə yaxşı vəziyyətdə saxlanılacaq.

Hər məmur yalnız bir ofis seçməlidir ki, yaxşı vəziyyətdə olan yolların ümumi uzunluğu maksimum olsun.

Giriş verilənləri

Birinci sətirdə boşluqla ayrılmış üç tam ədəd $N$, $M$ və $T$ verilir.

$N$ - qrafın zirvələrinin sayı ($N\le 100$);

$M$ - qrafın kənarlarının sayı ($M\le 1000$);

$T$ - məmurların sayı ($T\le 8$);

Sonra qrafın kənarlarını təsvir edən $M$ sətir gəlir. Hər bir kənar formatda verilir: $u_i$ $v_i$ $le{n}_i$, burada $le{n}_i$ - kənarın uzunluğu ($0\le u_i,v_i\le n$), ($le{n}_i\le 100000$).

Sonra $T$ tam ədəd olan sətir gəlir:

$0\le h_1,h_2,\dots ,h_t,\dots ,h_T\le n$ - məmurların evlərinin yerləşdiyi zirvələrin nömrələri;

Sonra $T$ tam ədəd olan sətir gəlir:

$0\le w_1,w_2,\dots ,w_t,\dots ,w_T\le n$ - məmurların gələcək iş yerlərinin yerləşdiyi zirvələrin nömrələri.

Çıxış verilənləri

$S$ - zəmanətli təmir olunacaq yolların maksimum ümumi uzunluğu.

$0\le w_{res,1},w_{res,2},\dots ,w_{res,t},\dots ,w_{res,T}\le n$ - zəmanətli təmir olunacaq yolların maksimum ümumi uzunluğuna uyğun gələn məmurların gələcək iş yerlərinin yerləşdiyi zirvələrin nömrələri.

Nümunələr