У нас є дерево з \(N\) вершинами під номерами \(1, 2, \dots, N\). \(i\)-е ребро (\(1 \leq i \leq N - 1\)) з'єднує вершину \(u_i\) і вершину \(v_i\) і має вагу \(w_i\).

Для різних вершин \(u\) і \(v\) нехай \(f(u, v)\) — найбільша вага ребра, що міститься на найкоротшому шляху від вершини \(u\) до вершини \(v\).

Знайти \(\displaystyle \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^N f(i, j)\).

Формат вхідних даних

Перший рядок містить ціле число \(N\) (\(2 \le N \le 10^5\))

Наступні  \(N-1\) рядків містять цілі числа \(u_i, v_i, w_i\) (\(1 \le u-i,v_i \le N\), \(1 \le w_i \le 10^7\))

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть шукану суму.

Примітка

До прикладу 1:

Маємо f(1, 2) = 10, f(2, 3) = 20 і f(1, 3) = 20 тому ми повинні вивести їх суму, тобто 50.

Приклад вхідних даних

3
1 2 10
2 3 20

Приклад вихідних даних

50

Приклад вхідних даних

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

Приклад вихідних даних

76