/*#include "factories.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vii vector<pii>
#define isz(x) (int)x.size()
using namespace std;
const int mxN = 5e5 + 5;
const ll oo = 1e18;
int n;
vector<vii> G;
vi vtn;
vector<vii> vt;
ll dis[mxN];
pii sparse[19][mxN];
int timer, ecnt, ap[mxN], dep[mxN], cur[mxN], tin[mxN], tout[mxN];
void dfs(int v, int p) {
tin[v] = ++timer;
dep[v] = dep[p] + 1;
sparse[0][++ecnt] = {dep[v], v};
ap[v] = ecnt;
for(auto &[u, w] : G[v]) {
if(u == p) continue;
dis[u] = dis[v] + p;
dfs(u, v);
sparse[0][++ecnt] = {dep[v], v};
}
tout[v] = ++timer;
}
void build_sparse() {
for(int p = 1, i = 1; p << 1 <= ecnt; p <<= 1, ++i)
for(int j = 1; j <= ecnt - (p << 1) + 1; ++j)
sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + p]);
}
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int LCA(int u, int v) {
int l = ap[u], r = ap[v];
if(l > r) swap(l, r);
int len = r - l + 1, lg_len = __lg(len);
return min(sparse[lg_len][l], sparse[lg_len][r - (1 << lg_len) + 1]).ss;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
G.resize(n); vt.resize(n);
for(int i = 0; i < N - 1; ++i) {
G[A[i]].emplace_back(B[i], D[i]);
G[B[i]].emplace_back(A[i], D[i]);
}
dfs(0, 0); build_sparse();
}
long long Query(int S, int X[], int T, int Y[]) {
queue<pii> q;
for(int i = 0; i < S; ++i) {
cur[X[i]] = 1;
q.emplace(X[i], 0);
vtn.emplace_back(X[i]);
}
for(int i = 0; i < T; ++i) {
cur[Y[i]] = 2;
vtn.emplace_back(Y[i]);
}
sort(all(vtn), [&](int u, int v) {
return tin[u] < tin[v];
});
for(int i = 0; i < S + T - 1; ++i) {
vtn.emplace_back(LCA(vtn[i], vtn[i + 1]));
}
sort(all(vtn), [&](int u, int v) {
return tin[u] < tin[v];
});
vtn.erase(unique(all(vtn)), vtn.end());
auto add_vt = [&](int u, int v, int w) {
vt[u].emplace_back(v, w);
vt[v].emplace_back(u, w);
};
stack<int> s;
for(int i = 0; i < isz(vtn); ++i) {
while(not s.empty() && not is_ancestor(s.top(), vtn[i])) s.pop();
if(s.empty()) s.emplace(vtn[i]);
else {
add_vt(s.top(), vtn[i], dis[vtn[i]] - dis[s.top()]);
s.emplace(vtn[i]);
}
}
ll res = oo;
auto dfs = [&](auto self, int v, int p) -> vll {
vll cur_dis(2, oo);
if(cur[v]) cur_dis[cur[v] - 1] = 0;
for(auto &[u, w] : G[v]) {
if(u == p) continue;
vll tmp = self(self, u, v);
for(int i = 0; i < 2; ++i)
cur_dis[i] = min(cur_dis[i], tmp[i] + w);
}
res = min(res, accumulate(all(cur_dis), 0LL));
return cur_dis;
};
dfs(dfs, vtn[0], 0);
for(int i = 0; i < S; ++i) {
cur[X[i]] = 0;
vt[X[i]].clear();
}
for(int i = 0; i < T; ++i) {
cur[Y[i]] = 0;
vt[Y[i]].clear();
}
vtn.clear();
return res;
}*/
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
long long int f[500005];
int n, d[500005], tin[500005], b[2000005], l[2000005], z = 0;
vector<int> gg[500005], g[500005];
int p[500005][20], pp[2000005][22];
void bfs(int x) {
queue<int> q;
q.push(x);
p[x][0] = x;
f[x] = d[x] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int j = 1; j <= 19; j++) {
p[u][j] = p[p[u][j - 1]][j - 1];
if (p[u][j] == 0) break;
}
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (d[u] + 1 < d[v]) {
d[v] = d[u] + 1;
f[v] = f[u] + gg[u][i];
p[v][0] = u;
q.push(v);
}
}
}
}
void dfs(int x, int p) {
b[++z] = x;
pp[z][0] = x;
tin[x] = z;
for (int w : g[x]) {
if (w == p) continue;
dfs(w, x);
b[++z] = x;
pp[z][0] = x;
}
b[++z] = x;
pp[z][0] = x;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i < 500000; i++) {
f[i] = 999999999999999999;
d[i] = n * 2;
}
for (int i = 0; i < n - 1; i++) {
int u = A[i], v = B[i], w = D[i];
g[u].push_back(v);
g[v].push_back(u);
gg[u].push_back(w);
gg[v].push_back(w);
}
bfs(0);
dfs(0, -1);
for (int i = 2; i <= 2000000; i++) l[i] = l[i / 2] + 1;
for (int i = 1; (1 << i) <= z; i++) {
for (int j = 1; j <= z - (1 << i) + 1; j++) {
if (d[pp[j][i - 1]] < d[pp[j + (1 << (i - 1))][i - 1]]) pp[j][i] = pp[j][i - 1];
else pp[j][i] = pp[j + (1 << (i - 1))][i - 1];
}
}
}
int lca(int u, int v) {
int x = tin[u], y = tin[v];
if (y <= x) swap(x, y);
int g = l[y - x + 1];
int h = pp[x][g], k = pp[y - (1 << g) + 1][g];
if (d[h] < d[k]) return h;
return k;
}
long long int check(int u, int v) {
return f[u] + f[v] - f[lca(u, v)] * 2;
}
long long int Query(int S, int X[], int T, int Y[]) {
if (S > 100 && T > 100) {
vector<long long int> ff(n, 999999999999999999);
vector<bool> dda(n, 0), dd(n, 0);
for (int i = 0; i < T; i++) {
dda[Y[i]] = 1;
}
priority_queue<pair<long long int, long long int>> q;
for (int i = 0; i < S; i++) {
q.push({0, X[i]});
ff[X[i]] = 0;
}
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (dd[u] == 1) continue;
dd[u] = 1;
if (dda[u] == 1) return ff[u];
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i], w = gg[u][i];
if (ff[u] + w < ff[v]) {
ff[v] = ff[u] + w;
q.push({-ff[v], v});
}
}
}
}
long long int res = 999999999999999999;
for (int i = 0; i < S; i++) {
for (int j = 0; j < T; j++) {
res = min(res, check(X[i], Y[j]));
}
}
return res;
}
