Алгоритm Yen

Giriş

Birinci sətirdə qrafın zirvələrinin sayı $n$ (1 \leq n \leq 100), qolların sayı $m$ (1 \leq m \leq 4000), və yolun sıra nömrəsi $k$ (1 \leq k \leq 500) verilir.

Növbəti $m$ sətirdə qrafın qolları verilir. Hər sətirdə üçlük (u, v, w) yazılır, bu, $u$ və $v$ zirvələrini birləşdirən və çəkisi $w$ olan qolu göstərir.

Sonuncu sətirdə yolun axtarılmalı olduğu iki zirvənin nömrələri $s$ və $t$ verilir.

Qrafda çoxlu qollar və döngələr ola bilməz. Bütün çəkilər müsbət və $10000$-dən çox deyil. Axtarılan yolun mövcudluğu təmin edilir.

Çıxış

Birinci sətirdə tapılmış yolun çəkisini və zirvələrin sayını iki rəqəm olaraq çıxarın.

Növbəti sətirdə yolun özünü — zirvələrin nömrələrinin ardıcıllığını çıxarın.

Nümunələr