// JOI14_factories
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;
#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'
#define MAXN 500100
#define LOGN 25
int n;
vector<pii> adj[MAXN];
vector<pll> cld[MAXN];
ll h[MAXN];
int sttime[MAXN], fntime[MAXN], timer;
int col[MAXN];
ll dp[2][MAXN];
ll ans;
int lpar[LOGN][MAXN];
int eh[MAXN];
bool cmp(int x, int y)
{
return sttime[x] < sttime[y];
}
int getlca(int u, int v)
{
if (eh[u] > eh[v]) swap(u, v);
FOR(i, 0, LOGN)
if ((eh[v] - eh[u]) >> i & 1)
v = lpar[i][v];
if (u == v) return u;
for (int i = LOGN - 1; i >= 0; i--)
if (lpar[i][v] != lpar[i][u])
u = lpar[i][u], v = lpar[i][v];
return lpar[0][u];
}
void dfs1(int v, int par)
{
sttime[v] = timer++;
for (pii p : adj[v])
{
int u = p.fr;
int w = p.sc;
if (u == par) continue;
h[u] = h[v] + w;
lpar[0][u] = v;
eh[u] = eh[v] + 1;
dfs1(u, v);
}
fntime[v] = timer;
}
void dfs2(int v)
{
if (col[v] == 1) dp[0][v] = 0;
else if (col[v] == 2) dp[1][v] = 0;
for (pll p : cld[v])
{
int u = p.fr;
ll w = p.sc;
dfs2(u);
dp[0][v] = min(dp[0][v], dp[0][u] + w);
dp[1][v] = min(dp[1][v], dp[1][u] + w);
}
ans = min(ans, dp[0][v] + dp[1][v]);
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
FOR(i, 0, n - 1)
{
int a = A[i] + 1;
int b = B[i] + 1;
adj[a].pb({b, D[i]});
adj[b].pb({a, D[i]});
}
dfs1(1, -1);
FOR(i, 1, LOGN)
FOR(j, 1, n + 1)
lpar[i][j] = lpar[i - 1][lpar[i - 1][j]];
}
ll Query(int s, int x[], int t, int y[])
{
vector<int> vec;
FOR(i, 0, s) vec.pb(x[i] + 1);
FOR(i, 0, t) vec.pb(y[i] + 1);
sort(all(vec), cmp);
int k = vec.size();
FOR(i, 1, k) vec.pb(getlca(vec[i], vec[i - 1]));
sort(all(vec), cmp);
vec.resize(unique(all(vec)) - vec.begin());
// clear stuff
for (int u : vec) cld[u].clear(), col[u] = 0, dp[0][u] = dp[1][u] = LINF;
ans = LINF;
vector<int> stk;
for (int v : vec)
{
while (stk.size() && fntime[stk.back()] < fntime[v]) stk.pop_back();
if (stk.size())
cld[stk.back()].pb({v, h[v] - h[stk.back()]});
stk.pb(v);
}
FOR(i, 0, s)
col[x[i] + 1] = 1;
FOR(i, 0, t)
col[y[i] + 1] = 2;
dfs2(vec[0]);
return ans;
}
/*
int _x[MAXN], _y[MAXN];
int _a[MAXN], _b[MAXN], _d[MAXN];
int32_t main(void)
{
fast_io;
int n, q;
cin >> n >> q;
FOR(i, 0, n - 1)
cin >> _a[i] >> _b[i] >> _d[i];
Init(n, _a, _b, _d);
FOR(i, 0, q)
{
int s, t;
cin >> s >> t;
FOR(j, 0, s)
cin >> _x[j];
FOR(j, 0, t)
cin >> _y[j];
cout << Query(s, _x, t, _y) << endl;
}
return 0;
}
*/
