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ələr