Dima və məşhur turist#2931
Məşhur turist Gennadi həmişə səyahətlərində ən qısa marşrutları seçir. Dima adlı bir oğlan isə Gennadinin pərəstişkarıdır və onunla bağlı əlində olan bütün məlumatları — istər qəzet kəsikləri, istərsə də internet xəbərləri və s. — toplayır.
Yaxınlarda Gennadi səfərə çıxıb. Yol boyu bəzi pərəstişkarları onu müəyyən şəhərlərdə görüblər və bu barədə bloqlarında yazıblar. Dima isə bu yazıların hamısını tapıb, lakin axtarışını səfər bitəndən sonra apardığı üçün qeydlərin xronoloji düzülüşünü bərpa edə bilmir — o yalnız Gennadinin mütləq hansı şəhərlərə baş çəkdiyini dəqiq bilir. O əmindir ki, Gennadi bir şəhərdən digərinə həmişə ən qısa yol ilə yollanıb. Dimaya Gennadinin mümkün hansısa bir marşrutunu bərpa etməkdə kömək edin.
Dima ancaq dəqiq mənbələrdən istifadə edir, ona görə də marşrutun mövcud olduğuna zəmanət verilir.
Birinci sətirdə və (1 \leq n, m \leq 10^5) — şəhərlərin və yolların sayı verilir. Növbəti sətrin hər birində yol təsviri verilir: a_i, b_i, t_i (a_i \neq b_i, 1 \leq a_i, b_i \leq n, 1 \leq t_i \leq 10^4) — yolun sonundakı şəhərlər və onun getmə müddəti. Daha sonra bir sətirdə — Gennadinin mütləq olduğu şəhərlərin sayı verilir. Sonuncu sətirdə həmin şəhərlərin nömrələri yazılmışdır. Hər şəhər bu siyahıda ən çoxu bir dəfə verilir.
Birinci sətirdə Gennadinin keçdiyi yolların sayını, ikinci sətirdə isə bu yolları Gennadinin keçdiyi ardıcıllıqla göstərin. Bir neçə həll mümkündürsə, istənilən birini çıxarın.
Nümunə 1