Дима və məşhur turist
Məşhur turist Gennadi səyahətlərində həmişə ən qısa yolları seçir. Dima adlı bir oğlan Gennadinin böyük pərəstişkarıdır və onun haqqında əldə edə bildiyi bütün məlumatları toplayır — qəzet kəsikləri, internet xəbərləri və s.
Son zamanlarda Gennadi bir səyahətə çıxdı. Yolda bəzi şəhərlərdə onu pərəstişkarları gördü və bu barədə bloqlarında yazdılar. Dima bu xatirələrin hamısını tapdı, lakin axtarışını səyahət bitdikdən sonra apardığı üçün qeydlərin xronoloji ardıcıllığını bərpa edə bilmədi — yalnız Gennadinin dəqiq olduğu şəhərlərin dəstini bilir. Ona dəqiq məlumdur ki, Gennadi bir şəhərdən digərinə ən qısa yolla səyahət edib. Dimaya Gennadinin mümkün olan bir yolunu qurmağa kömək edin.
Dima yalnız etibarlı mənbələrdən istifadə edir, belə ki, yolun mövcudluğu zəmanətlidir.
Giriş verilənləri
Birinci sətir 2 tam ədəd n və m (1 ≤ n, m ≤ 10^5) — şəhərlərin və yolların sayını ehtiva edir. Növbəti m sətirin hər biri bir yolun təsvirini ehtiva edir a_i, b_i, t_i (a_i ≠ b_i, 1 ≤ a_i, b_i ≤ n, 1 ≤ t_i ≤ 10^4) — yolun sonundakı şəhərlər və bu yolda səyahət müddəti. Növbəti sətir k — Gennadinin dəqiq ziyarət etdiyi şəhərlərin sayını ehtiva edir. Sonuncu sətir bu şəhərlərin nömrələrini ehtiva edir. Bu siyahıdakı hər bir şəhər ən çox bir dəfə görünür.
Çıxış verilənləri
Birinci sətirdə Gennadinin keçdiyi yolların sayını, ikinci sətirdə isə bu yolları Gennadinin ziyarət ardıcıllığı ilə göstərin. Əgər bir neçə həll mövcuddursa — istənilənini göstərin.