Məsələlər
Cəm
Cəm
Romanın valideynləri ona $n$ sayda təpəsi və $n - 1$ sayda tilləri olan istiqamətlənməmiş əlaqəli çəkili qraf hədiyyə edirlər. Roman qrafda olan bütün yolların ümumi uzunluğunu tapmaq istəyir. Yolun uzunluğu onda olan tillərin uzunluqlarının cəmidir. Roman hesab edir ki, $u$-dan $v$-yə olan yol $v$-dən $u$-ya olan yol kimidir, buna görə də o onları fərqləndirmir.
\InputFile
İlk sətir qrafda olan təpələrin $n\:(2 \le n \le 10^5)$ sayını ehtiva edir. Növbəti $n - 1$ sətir qrafın tillərini təsvir edir. Hər sətir üç tam ədəd ehtiva edir: Tilin birləşdirdiyi təpələrin nömrələri (təpələr $1$-dən $n$-ə qədər nömrələnib) və tilin çəkisi.
\OutputFile
Bütün yolların uzunluqlarının cəmini $10^9$ moduluna görə hesablayın.
\includegraphics{https://static.e-olymp.com/content/1c/1c9962225b484b4be775b21ea4f0cae761cb1c5a.gif}
Giriş verilənləri #1
3 1 2 1 1 3 3
Çıxış verilənləri #1
8
Giriş verilənləri #2
6 1 2 5 1 3 1 2 4 2 2 5 4 2 6 3
Çıxış verilənləri #2
90
Şərh: Məsələnin izahı. Qrafda olan bütün yollar: 1 → 2, 1 → 3, 2 → 1 → 3, onların uzunluqlarının cəmi 1 + 3 + 4 = 8.