Descripción

La escuela donde impartes clases está organizando una salida al Jardín Botánico de Chapultepek (no debe confundirse con Chapultepec). Este jardín está formado por $N$ sectores para visitar, convenientemente enumerados del $1$ al $N$. Adicionalmente, todos los sectores están conectados por senderos, los cuales tienen arreglos de flores de distinta belleza. Sabemos que entre cada par de sectores hay exactamente un camino que no repite senderos.

Al recorrer un camino de varios senderos para ir del sector $A$ al sector $B$ se pasa por senderos de posiblemente distintas bellezas. Como un sendero de mayor belleza eclipsa totalmente a uno de menor belleza, decimos que la belleza de un camino es la máxima belleza de los senderos que lo conforman. Le llamaremos a esa belleza $beau(A,B)$.

Coincidentemente, te das cuenta que tienes una cantidad de alumnos igual al número total de caminos que hay en el jardín. Como maestro, te preguntas cuál es la belleza total que verán tus alumnos si envías a cada uno a recorrer un camino distinto. Es decir, te preguntas cuánto es $$\sum_{i = 1}^N \sum_{j = i + 1}^Nbeau(i,j)$$.

Entrada

La primera línea tiene el número $N$ de sectores. Las siguientes $N-1$ líneas son 3 enteros por línea $x_i, y_i, b_i$, indicando que hay un sendero de $x_i$ a $y_i$ cuyas flores tienen una belleza de $b_i$.

Salida

Un solo número, indicando la belleza total. Para evitar trabajar con números grandes, imprime la belleza total módulo 1000000007 ($10^9+7$).

Ejemplo

5
1 2 1
1 3 1
2 4 2
2 5 2

17

Límites

• $1 \leq x_i, y_i \leq N $
• $1 \leq b_i \leq 10^9 $
• Subtarea 1 con un total de 20 puntos
  • $3 \leq N \leq 200$
• Subtarea 2 con un total de 20 puntos
  • $3 \leq N \leq 2,000$
• Subtarea 3 con un total de 60 puntos
  • $3 \leq N \leq 10^5$