#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
#define FOR(i, a, b) for(int i = a, _b = b; i <= (_b); i++)
#define FORD(i, a, b) for(int i = a, _b = b; i >= (_b); i--)
#define ALL(A) A.begin(), A.end()
#define fi first
#define se second
#define pb push_back
const int maxn = 5e5 + 5;
int n, q;
vector <array <int, 2>> g[maxn];
int sz[maxn], is_centroid[maxn];
int par[maxn];
int P[maxn][20], h[maxn];
long long sum[maxn];
void dfs(int u, int p){
sz[u] = 1;
for(auto it : g[u]){
int v = it[0];
if(v == p || is_centroid[v]) continue;
dfs(v, u);
sz[u]+= sz[v];
}
}
int findCentroid(int u, int p, int big){
for(auto it : g[u]){
int v = it[0];
if(v == p || is_centroid[v]) continue;
if(sz[v] > big / 2) return findCentroid(v, u, big);
}
return u;
}
void buildCentroid(int u, int preCentroid){
dfs(u, - 1);
int centroid = findCentroid(u, - 1, sz[u]);
is_centroid[centroid] = true;
par[centroid] = preCentroid;
for(auto it : g[centroid]){
int v = it[0];
if(is_centroid[v]) continue;
buildCentroid(v, centroid);
}
}
const int N = 5e5 + 5;
struct LowestCommonAncestor
{
vector <int> nList, hList;
int tin[N], tout[N], timeDFS;
int rmq[4 * N][24];
int h[N];
ll sum[N];
void dfs(int u,int p)
{
nList.pb(u); hList.pb(h[u]);
tin[u] = ++ timeDFS;
for(auto x :g[u])
{
int v= x[0], w = x[1];
if(v==p) continue;
h[v] = h[u] + 1;
sum[v] = sum[u] + w;
dfs(v,u);
nList.pb(u); hList.pb(h[u]);
}
tout[u] = ++timeDFS;
}
int merge(int i,int j)
{
return (hList[i] < hList[j] ? i : j);
}
void init()
{
nList.pb(0); hList.pb(0);
dfs(1,1);
int m = nList.size()-1;
FOR(i,1,m) rmq[i][0] = i;
for(int j =1;(1<<j)<=m;j++) FOR(i,1,m-(1<<j)+1)
{
rmq[i][j] =merge(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
}
}
int lca(int u,int v)
{
if(tin[u] > tin[v]) swap(u, v);
int k = __lg(tin[v]-tin[u]+1);
return nList[merge(rmq[tin[u]][k], rmq[tin[v]-(1<<k)+1][k])];
}
ll dist(int u,int v)
{
return sum[u] + sum[v] - 2 * sum[lca(u, v)];
}
} LCA;
set <pair <long long, int>> best[maxn];
long long bestMinSon[maxn];
void update(int u){
int son = u, v = par[u];
for(; v; v = par[v]){
long long cost = LCA.dist(u, v);
if(bestMinSon[son] > cost){
best[v].erase({bestMinSon[son], son});
bestMinSon[son] = cost;
best[v].insert({bestMinSon[son], son});
}
son = v;
}
}
bool ok[maxn];
void del(int u){
int son = u, v = par[u];
for(; v; v = par[v]){
best[v].clear();
bestMinSon[son] = 1e18;
son = v;
}
}
long long get(int u){
long long res = 1e18;
if(best[u].size()){
res = min(res, best[u].begin() -> first);
}
int son = u, v = par[u];
for(; v; v = par[v]){
long long cost = LCA.dist(u, v);
if(ok[v]){
res = min(res, cost);
}
if(best[v].size()){
if(best[v].begin() -> second == son){
auto it = best[v].begin();
it++;
if(it != best[v].end()){
res = min(res, cost + it -> first);
}
} else{
res = min(res, cost + best[v].begin() -> first);
}
}
}
return res;
}
void process(void){
buildCentroid(1, 0);
LCA.init();
memset(bestMinSon, 0x3f, sizeof bestMinSon);
// while(q--){
// int numS, numT; cin >> numS >> numT;
// vector <int> vers;
// FOR(i, 1, numS){
// int u; cin >> u; u++;
// vers.push_back(u);
// ok[u] = 1;
// update(u);
// }
// long long ans = 1e18;
// FOR(i, 1, numT){
// int u; cin >> u; u++;
// ans = min(ans, get(u));
// }
// cout << ans << "\n";
// for(int &u : vers){
// ok[u] = 0;
// del(u);
// }
// }
}
void Init(int N, int A[], int B[], int D[]){
n = N;
FOR(i, 1, n - 1){
int u = A[i - 1], v = B[i - 1], w = D[i - 1];
u++; v++;
g[u].push_back({v, w}); g[v].push_back({u, w});
}
process();
}
long long Query(int S, int X[], int T, int Y[]){
FOR(i, 0, S - 1){\
ok[X[i] + 1] = 1;
update(X[i] + 1);
}
long long res = 1e18;
FOR(i, 0, T - 1){
res = min(res, get(Y[i] + 1));
}
FOR(i, 0, S - 1){
del(X[i] + 1);
ok[X[i] + 1] = 0;
}
return res;
}
// signed main(void){
// ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
// #define taskname "kieuoanh"
// if(fopen(taskname".inp", "r")){
// freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
// }
// cin >> n >> q;
// FOR(i, 1, n - 1){
// int u, v, w; cin >> u >> v >> w;
// ++u; ++v;
// g[u].push_back({v, w}); g[v].push_back({u, w});
// }
// process();
// return 0;
// }
