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.
Giriş verilənləri
İ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.
Çıxış verilənləri
Bütün yolların uzunluqlarının cəmini 10^9 moduluna görə hesablayın.
Nümunə
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