F. Minimize Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a weighted undirected tree of N nodes, rooted at the node 1. You can remove at most 1 edge and add another edge of same weight such that the resulting graph is still a tree. Minimize the sum of distances from node 1 to all other nodes.

Input

The first line contains a single integer N, the size of the tree. Next N - 1 lines contain three space separated integers u, v and w, denoting an edge between the vertices u and v of weight w.

Constraints: 1 ≤ N ≤ 5 × 104, 1 ≤ u, v ≤ N,  - 103 ≤ w ≤ 103

Output

Output a single integer, the minimum sum of distances from node 1 to all other nodes.

Examples
Input
2
1 2 3
Output
3
Input
4
1 2 61
1 3 -14
3 4 -47
Output
-75