We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Tree Flow

Tree Flow

Recall that a tree is an undirected, connected acyclic graph. We have a weighted tree, , with vertices; let be the total sum of edge weights on the path between nodes and .

Let's consider all the matrices, , such that:

  • for each and

We consider the total value of matrix to be:

Calculate and print the maximum total value of for a given tree, .

Input Format

The first line contains a single positive integer, , denoting the number of vertices in tree .
Each line of the subsequent lines contains three space-separated positive integers denoting the respective , , and values defining an edge connecting nodes and (where ) with edge weight .

Constraints

  • Test cases with have of total score
  • Test cases with have of total score

Output Format

Print a single integer denoting the maximum total value of matrix satisfying the properties specified in the Problem Statement above.

Sample Input

3
1 2 2
1 3 1

Sample Output

3

Explanation

In the sample case, matrix is:

The sum of the elements of the first row is equal to .