eolymp
bolt
Try our new interface for solving problems

Cəm

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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
Mənbə 2011 International Collegiate Programming Contest, Ukraine, Quarter-Final, May 19