[Solution] Journey Codeforces Solution | Solution Codeforces

J. Journey

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

One day, Pak Chanek who is already bored of being alone at home decided to go traveling. While looking for an appropriate place, he found that Londonesia has an interesting structure.

According to the information gathered by Pak Chanek, there are 𝑁$N$ cities numbered from 1$1$ to 𝑁$N$. The cities are connected to each other with 𝑁−1$N-1$ two-directional roads, with the 𝑖$i$-th road connecting cities 𝑈𝑖$U_i$ and 𝑉𝑖$V_i$, and taking a time of 𝑊𝑖$W_i$ hours to be traversed. In other words, Londonesia's structure forms a tree.

Pak Chanek wants to go on a journey in Londonesia starting and ending in any city (not necessarily the same city) such that each city is visited at least once with the least time possible. In order for the journey to end quicker, Pak Chanek also carries an instant teleportation device for moving from one city to any city that can only be used at most once. Help Pak Chanek for finding the minimum time needed.

Notes:

• Pak Chanek only needs to visit each city at least once. Pak Chanek does not have to traverse each road.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

• In the journey, a city or a road can be visited more than once.

Input

The first line contains a single integer 𝑁$N$ (1≤𝑁≤105$1\le N\le {10}^5$) — the number of cities in Londonesia.

The 𝑖$i$-th of the next 𝑁−1$N-1$ lines contains three integers 𝑈𝑖$U_i$, 𝑉𝑖$V_i$, and 𝑊𝑖$W_i$ (1≤𝑈𝑖,𝑉𝑖≤𝑁$1\le U_i,V_i\le N$, 1≤𝑊𝑖≤109$1\le W_i\le {10}^9$) — a two-directional road that connects cities 𝑈𝑖$U_i$ and 𝑉𝑖$V_i$ that takes 𝑊𝑖$W_i$ hours to be traversed. The roads in Londonesia form a tree.

Output

Output one integer, which represents the minimum time in hours that is needed to visit each city at least once.