Qəzet daşıyan
Hər hansı müasir kasıb tələbə kimi, siz də qəzet daşıyıcısı kimi qismən işlə məşğul olmağa qərar verdiniz. İşə qəbul olunmusunuz və sizə marşrut təsviri təqdim edilib: 1 -dən n -ə qədər nömrələrlə işarələnmiş ünvanlar dəsti.
Hər səhər qəzet redaksiyasında işə başlayırsınız (bu yer marşrut təsvirində 0 nömrəsi ilə işarələnib). Sizə verilmiş hər bir ünvana qəzet çatdırmaq üçün marşrut planlaşdırmalısınız və işinizi bitirdikdən sonra dərhal təhsil yerinə çatmaq istəyirsiniz. Şanslısınız ki, xidmət göstərdiyiniz ünvanlar bölgəsində yalnız n yol var və hər biri üçün təhsil yerinə çatmaq üçün lazım olan vaxt məlumdur.
Bundan əlavə, bəzi nöqtələrdən digər nöqtələrə, o cümlədən qəzet redaksiyasından, bəlkə də əlverişli nəqliyyat vasitələrindən istifadə edərək: velosiped, skeyt və ya avtostopla nə qədər tez çatmaq mümkün olduğu barədə məlumatlar var. Bütün qəzetləri nə qədər tez çatdırıb təhsil müəssisəsinə çata bilərsiniz?
Giriş verilənləri
Birinci sətirdə ünvanların sayı n (1 ≤ n ≤ 100000) verilib.
Növbəti n + 1 sətirdə bir tam ədəd c_i (nömrələmə i = 0 -dan başlayır, 0 ≤ c_i ≤ 1000000000) - təhsil müəssisəsinə i nömrəli nöqtədən çatmaq üçün lazım olan vaxt.
Daha sonra n sətir var, hər birində üç tam ədəd a, b, c (0 ≤ a, b ≤ n, a ≠ b, 0 ≤ c ≤ 1,000). Bu sətirlərin hər biri iki nöqtə arasında yolu təsvir edir, a -dan b -yə keçmək üçün lazım olan vaxtı c dəqiqə ilə göstərir.
Bütün ünvanlara çatmaq mümkün olduğu təmin edilir. (Unutmayın ki, qəzet redaksiyası 0 nöqtəsində yerləşir).
Çıxış verilənləri
Bütün poçtları çatdırmaq və təhsil yerinə çatmaq üçün lazım olan minimal vaxtı göstərin.
Misal üçün qeyd: Bu misalda, hər ünvana baş çəkdikdən sonra redaksiyaya qayıtmaq və təhsil yerinə də oradan getmək daha yaxşıdır. Məsələn, belə bir marşrutla: 0 -> 1 -> 0 -> 2 -> 0 -> Təhsil müəssisəsi = 1 + 1 + 2 + 2 + 1 = 7.