Taksi

Giriş

Birinci sətirdə beş ədəd verilir: dörd tam və bir həqiqi:

• $n$ — yaşayış məntəqələrinin sayı,

• $A$ — İvanın yaşadığı yaşayış məntəqəsinin nömrəsi,

• $B$ — Sergeyın yaşadığı yaşayış məntəqəsinin nömrəsi,

• $C$ — olimpiadanın keçirildiyi yaşayış məntəqəsinin nömrəsi,

• $d$ — taksi ilə bir kilometr səfərin qiyməti.

İkinci sətirdə tam ədəd $m$ — yolların sayı verilir.

Daha sonra hər biri bir yolu təsvir edən $m$ sətir gəlir: iki tam ədəd — onu birləşdirən yaşayış məntəqələrinin nömrələri və bir həqiqi ədəd — bu yolun uzunluğu kilometrlərlə.

Bütün yaşayış məntəqələrinin nömrələri $100$-dən çox olmayan natural ədədlərdir.

Çıxış

Bir həqiqi ədəd çıxarın — Sergeyı götürməyə gedən marşrutun birbaşa marşrutdan daha baha olduğu məbləği.

Əgər $A$ məntəqəsindən $B$ məntəqəsinə və ya $A$ məntəqəsindən $C$ məntəqəsinə marşrut mövcud deyilsə, $-1$ çıxarın.

Nümunələr