Taksi
İvan və Sergey informatika üzrə vilayət olimpiadasına dəvət alıblar. Onlar fərqli yaşayış məntəqələrində yaşadıqları üçün İvan, olimpiadanın keçiriləcəyi yerə çatmaq üçün taksi xidmətindən istifadə etməyi təklif edir.
Taksi əvvəlcə İvanın yaşadığı A məntəqəsindən çıxır, sonra Sergey'i götürmək üçün B məntəqəsinə gedir və nəhayət olimpiadanın keçiriləcəyi C məntəqəsinə yola düşür.
Vilayətdəki yaşayış məntəqələri arasındakı yolların uzunluğunu və taksi ilə bir kilometr yolun qiymətini nəzərə alaraq, İvanın Sergey'i götürmək üçün nə qədər əlavə pul xərclədiyini, birbaşa olimpiadanın keçiriləcəyi yerə getməkdən fərqli olaraq hesablayın.
Qeyd edək ki, taksi həmişə mövcud olan ən qısa marşrutu seçir.
Giriş məlumatları
Birinci sətirdə beş ədəd - dörd tam və bir onluq ədəd verilir:
n – yaşayış məntəqələrinin sayı,
A – İvanın yaşadığı məntəqə,
B – Sergey'in yaşadığı məntəqə,
C – Olimpiadanın keçiriləcəyi məntəqə,
d – taksi ilə 1 kilometr yolun qiyməti.
Növbəti sətir yolların sayı m-i göstərir. Sonrakı m sətirin hər biri bir yolu təsvir edir – iki tam ədəd (yolu birləşdirən yaşayış məntəqələrinin nömrələri) və onluq ədəd - müvafiq yolun uzunluğu kilometr ilə.
Bütün tam ədədlər təbii və 100-dən böyük deyil.
Çıxış məlumatları
Sergey'i götürmək üçün nə qədər əlavə pul ödəməli olduğunu göstərən onluq ədəd çıxarın və ya əgər A məntəqəsindən Sergey'in yaşadığı məntəqəyə və ya A məntəqəsindən olimpiadanın keçiriləcəyi yerə marşrut yoxdursa –1 çıxarın.