//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#include "factories.h"
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 5e5, cbit = 19;
const long long oo = 1e18;
vector<pair<int, int> > Adj[N + 1];
long long dp[N + 1], sum[N + 1];
int f[2 * N + 1][cbit + 1], par[N + 1], sz[N + 1], depth[N + 1], timer, logg[2 * N + 1], pos[N + 1];
bool visited[N + 1];
void DFS(int u, int p)
{
f[++timer][0] = u;
logg[timer] = logg[timer >> 1] + 1;
pos[u] = timer;
dp[u] = oo;
for (auto x : Adj[u])
{
int v = x.first, w = x.second;
if (v == p)
{
continue;
}
f[++timer][0] = u;
logg[timer] = logg[timer >> 1] + 1;
depth[v] = depth[u] + 1;
sum[v] = sum[u] + w;
DFS(v, u);
}
}
int LCA(int u, int v)
{
if (pos[u] > pos[v])
{
swap(u, v);
}
int k = logg[pos[v] - pos[u] + 1];
u = f[pos[u]][k];
v = f[pos[v] - (1 << k) + 1][k];
if (depth[u] < depth[v])
{
return u;
}
return v;
}
long long dis(int u, int v)
{
return sum[u] + sum[v] - 2 * sum[LCA(u, v)];
}
void CenDFS(int u, int p)
{
sz[u] = 1;
for (auto l : Adj[u])
{
int v = l.first, w = l.second;
if (visited[v] || v == p)
{
continue;
}
CenDFS(v, u);
sz[u] += sz[v];
}
}
int Find_Centroid(int u, int p, int x)
{
for (auto l : Adj[u])
{
int v = l.first, w = l.second;
if (visited[v] || v == p)
{
continue;
}
if (sz[v] > x/2)
{
return Find_Centroid(v, u, x);
}
}
return u;
}
int BuildCentroid(int u)
{
CenDFS(u, -1);
int root = Find_Centroid(u, -1, sz[u]);
visited[root] = true;
//cerr << root << '\n';
for (auto l : Adj[root])
{
int v = l.first, w = l.second;
if (visited[v])
{
continue;
}
par[BuildCentroid(v)] = root;
}
return root;
}
void Init(int N, int A[], int B[], int D[])
{
for (int i = 0; i < N - 1; ++ i)
{
Adj[A[i]].push_back({B[i], D[i]});
Adj[B[i]].push_back({A[i], D[i]});
}
logg[0] = -1;
DFS(0, -1);
par[BuildCentroid(0)] = -1;
for (int k = 1; k <= logg[timer]; ++ k)
{
for (int i = 1; i <= timer; ++ i)
{
int j = i + (1 << (k - 1));
if (j > timer)
{
f[i][k] = f[i][k - 1];
}
else
{
int u = f[i][k - 1], v = f[j][k - 1];
if (depth[u] < depth[v])
{
f[i][k] = u;
}
else
{
f[i][k] = v;
}
}
}
}
}
void update(int u, int t)
{
for (int v = u; v != -1; v = par[v])
{
if (t)
{
dp[v] = min(dp[v], dis(u, v));
}
else
{
dp[v] = oo;
}
}
}
long long get(int u)
{
long long ret = oo;
for (int v = u; v != -1; v = par[v])
{
ret = min(ret, dp[v] + dis(u, v));
}
return ret;
}
long long Query(int S, int X[], int T, int Y[])
{
long long res = oo;
for (int i = 0; i < S; ++ i)
{
update(X[i], 1);
}
for (int i = 0; i < T; ++ i)
{
res = min(res, get(Y[i]));
}
for (int i = 0; i < S; ++ i)
{
update(X[i], 0);
}
return res;
}
/*void read()
{
int A[] = {0, 1, 2, 2, 4, 1};
int B[] = {1, 2, 3, 4, 5, 6};
int D[] = {4, 4, 5, 6, 5, 3};
Init(7, A, B, D);
int X[] = {0, 1, 3};
int Y[] = {4, 6};
cout << Query(3, X, 2, Y);
}
void solve()
{
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
//freopen(TASK".OUT", "w", stdout);
}
int t = 1;
bool typetest = false;
if (typetest)
{
cin >> t;
}
for (int __ = 1; __ <= t; ++ __)
{
//cout << "Case " << __ << ": ";
read();
solve();
}
}*/
