سلطان و سلطانه به تازگی با هم ازدواج کرده‌اند. این دو یک‌دیگر را در سلطان‌آباد گم کردند. سلطان‌آباد $n$ شهر دارد که برخی از آن‌ها با جاده‌ی ۲ طرفه به هم وصل هستند. طول هر جاده نیز یک عدد طبیعی است. سلطان در شهر $X$ قرار دارد و سلطانه در شهر $Y$ گم شده است. سلطان می‌خواهد به شهر $Y$ برود و خانومش را پیدا کند. از آن‌جایی که این دو به تازگی ازدواج کرده‌اند و با وضع بسیار متعادل دلار، بدیهی است که این دو ماشین دارند، اما در پارکینگ است!
سلطان تصمیم می‌گیرد از تاکسی استفاده کند. در هر شهر یک تاکسی وجود دارد. راننده‌ی تاکسی شهر $i$، می‌تواند سلطان را از شهر $i$ به شهری دیگر با فاصله‌ی حداکثر $t_i$ ببرد. (فاصله‌ی دو شهر، برابر با طول کوتاه‌ترین مسیر وزن‌دار بین آن دو شهر است). هزینه‌ی تاکسی شهر $i$ نیز، ربطی به مسیر طی شده ندارد و برابر با $c_i$ است. هر تاکسی حداکثر یک‌بار می‌تواند استفاده شود. امکان پیاده شدن، فقط در شهرها وجود دارد و وسط جاده‌ها نمی‌توان پیاده شد. کمینه‌ی هزینه‌ای که سلطان برای رسیدن به معشوقش نیاز دارد، چقدر است؟