Summing Train Journey Joy

In IOI country, there are N cities and N-1 bidirectional railways connecting them such that any two different cities are connected by a unique simple path (i.e. the network forms a tree). The cities are numbered from 0 to N-1 and the railways are numbered from 0 to N-2. For each railway i, it connects cities U[i] and V[i] with a length of W[i].

From any city, there exists a direct train to any other city. For a direct train from city u to city v (with u ≠ v), the travel time is defined as the sum of the lengths of the railways along the unique simple path between them. As a railway enthusiast, you enjoy taking longer journeys. Thus, for two different cities x and y, the joy function joy(x, y) is defined as the maximum positive integer D such that it is possible to travel from x to y using one or more direct trains where each direct train has a travel time of at least D.

Note that one valid journey from x to y is simply taking the direct train from x to y, whose travel time is the distance d(x,y) along the unique path. Thus, it is clear that for any pair of different cities,
\[ joy(x,y)=d(x,y). \]

Your task is to compute the sum of joy(x, y) for all N(N-1) ordered pairs of distinct cities and output the result modulo \(10^9+7\).

You need to implement the following function:

int travel(std::vector<int> U, std::vector<int> V, std::vector<int> W);

The function is called only once. The input vectors U, V, and W each have size N-1 representing the railways. For every valid index i (0 ≤ i ≤ N-2), there is a railway connecting cities U[i] and V[i] with length W[i].

The function should return the sum of joy(x, y) for all ordered pairs of cities (x, y) with 0 ≤ x, y ≤ N-1 and x ≠ y, taken modulo \(10^9+7\).

inputFormat

The input is given as three vectors (or arrays) U, V, and W each of length N-1 representing a tree of N cities.
Note: The cities are numbered from 0 to N-1 and every pair of different cities is directly connected by a train whose travel time is defined by the sum of rail lengths along the unique path.

outputFormat

Return a single integer which is the sum of joy(x, y) for all ordered pairs (x, y) with x ≠ y, modulo \(10^9+7\).

sample

U = [0],
V = [1],
W = [5]

10