Qəzet daşıyan#2641
Kasib, təhsil haqqı ödənilən bir tələbə kimi, qəzet daşıyıcısı kimi yarımştat işə başlamağa qərar vermisən. Səni işə götürüblər və sənə qəzet marşrutu verilib: ünvanlar bir-birinin ardınca -dən -ə qədər nömrələnib.
Hər səhər qəzet ofisindən (marşrut təsvirində bu ünvan ilə işarələnir) başlayırsan. Hər ünvana qəzet çatdırmalı, sonra isə dərhal oxuduğun yerə çatmalısan. Xoşbəxtlikdən, xidmət edilən ünvanlar arasında cəmi yol var və onların hər biri üzrə hərəkət etmək üçün lazım olan vaxt məlumdur.
Bundan əlavə, bəzi nöqtələrdən, o cümlədən qəzet ofisindən, məsələn, velosiped, skeytbord və ya avtostop ilə, bir başqasına nə qədər tez çata biləcəyin barədə də məlumatlar var. Bütün qəzetləri çatdırıb oxuduğun yerə çatmaq üçün lazım olan minimal vaxt nə qədərdir?
Birinci sətirdə ünvanların sayı (1 \leq n \leq 100000) verilir.
Növbəti n + 1 sətirin hər birində bir tam ədəd c_i var (burada nömrələmə i = 0-dan başlayır, 0 \leq c_i \leq 1000000000)—-ci ünvandan oxuduğun yerə çatmaq üçün lazım olan vaxt.
Bundan sonra sətir verilir, hər birində üç tam ədəd , , var (0 \leq a, b \leq n, a \neq b, 0 \leq c \leq 1000). Hər sətir iki nöqtə arasındakı yolu təsvir edir, -dan -yə keçmək üçün lazım olan vaxt dəqiqədir.
Bütün ünvanlara çatmaq mümkün olduğu zəmanət verilir. (Qəzet ofisinin nömrəli ünvanda olduğunu unutma.)
Bütün qəzetləri çatdırıb oxuduğun yerə çatmaq üçün lazım olan minimal vaxtı çap et.
Qeyd: Bu nümunədə hər ünvana baş çəkib, ofisə qayıdıb, sonra oxuduğun yerə getmək daha əlverişlidir. Məsələn, aşağıdakı marşrutu istifadə edərək: 0 \to 1 \to 0 \to 2 \to 0 \to oxuduğun yer = 1 + 1 + 2 + 2 + 1 = 7.
Nümunə 1