h2. Date de intrare

Fişierul de intrare $arbori3.in$ conţine mai multe exemple de test. Un exemplu are o linie conţinând un singur număr natural <tex>n</tex>, urmată de <tex>n-1</tex> linii conţinând fiecare trei întregi <tex>X</tex>, <tex>Y</tex> şi <tex>L</tex> separaţi de un spaţiu şi reprezentând un arc al arborelui între nodurile <tex>X</tex> şi <tex>Y</tex>, având lungimea <tex>L</tex>. Fişierul se termină cu o linie conţinând un singur 0.

Fişierul de intrare $arbori3.in$ ...

h2. Date de ieşire

Fişierul de ieşire $arbori3.out$ conţine câte o linie pentru fiecare exemplu de test, pe care se tipăreşte suma distanţelor <tex>D(P_i)</tex> pentru toate cele <tex>n!</tex> permutări luată modulo **9999991**.

În fişierul de ieşire $arbori3.out$ ...

h2. Restricţii

* <tex>2 \leq n \leq 10^5</tex>
* <tex>1 \leq L \leq 10^6</tex>
* numărul de teste nu depăşeşte 20

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. arbori3.in |_. arbori3.out |

| 3
1 2 1
1 3 2
0
| 24

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="arbori3") ==