Metro

Metro sistemi $L$ xəttdən ibarətdir və $N$ stansiyası var, stansiyalar $1$-dən $N$-ə qədər nömrələnib. Hər bir stansiya bir və ya bir neçə xəttə aid ola bilər. Əgər bir stansiya bir neçə xətt tərəfindən paylaşılırsa, o zaman bu stansiya kəsişmə nöqtəsidir və həmin xətlər arasında keçidi təmin edir. Hər bir xətt azı iki stansiyadan ibarətdir və ən azı bir kəsişmə stansiyası var. Metro sistemi bağlıdır, yəni istənilən iki stansiya arasında yol var. Səyahət üçün ödəniş aşağıdakı iki variantdan kiçiyi ilə hesablanır:

1. Marşrutda istifadə olunan hər bir stansiyaya (başlanğıc və son stansiyalar daxil olmaqla) görə $A$ qəpik.

2. Marşrutda istifadə olunan hər bir xəttə görə $B$ qəpik.

Stansiya $i$-dən stansiya $j$-yə getmək üçün tələb olunan ən az qəpiyi müəyyən edin.