#include <bits/stdc++.h>
#include "factories.h"
#define ii pair <int, long long>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;
#define _ << ", " <<
using namespace std;
inline void read(int &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void read(long long &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void writeln(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar('\n');}
inline void write(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar(' ');}
const int N = 5e5 + 7;
const int LOG = log2(N) + 7;
const long long oo = 1e18 + 7;
int n, q, nNode, Time;
long long dist;
int nChild[N], d[N], D[N];
int p[N][LOG + 7];
bool blocked[N];
vector <ii> adj[N];
vector <ii> Adj[N];
int X[N], Y[N], t[N];
long long f[N];
int par[N];
void DFS(int u){
for (auto t: adj[u]){
int v = t.x;
int w = t.y;
if (!d[v]){
d[v] = d[u] + 1;
p[v][0] = u;
D[v] = D[u] + w;
DFS(v);
}
}
}
void dfs(int u, int p){
nNode++;
nChild[u] = 1;
for (auto t: adj[u]){
int v = t.x;
if (v != p && !blocked[v]){
dfs(v, u);
nChild[u] += nChild[v];
}
}
}
int getCentroid(int u, int p){
for (auto t: adj[u]){
int v = t.x;
int w = t.y;
if (v != p && !blocked[v])
if (nChild[v] > nNode / 2){
dist += w;
return getCentroid(v, u);
}
}
return u;
}
inline void addEdge(int u, int v, long long w){
Adj[u].push_back(ii(v, w));
Adj[v].push_back(ii(u, w));
}
void buildTree(int u, int p, int c, int dd){
nNode = 0;
dfs(u, u);
dist = dd;
int centroid = getCentroid(u, p);
if (c != -1){
addEdge(centroid, c, dist);
par[centroid] = c;
}
else
par[centroid] = -1;
blocked[centroid] = true;
for (auto t: adj[centroid]){
int v = t.x;
int w = t.y;
if (v != p && !blocked[v])
buildTree(v, centroid, centroid, w);
}
}
void Move(int &u, int d){
for (int i = LOG; i >= 0; i--)
if (d & (1 << i))
u = p[u][i];
}
int LCA(int u, int v){
if (d[u] > d[v])
Move(u, d[u] - d[v]);
else
Move(v, d[v] - d[u]);
if (u == v) return u;
for (int i = LOG; i >= 0; i--)
if (p[u][i] != p[v][i]){
u = p[u][i];
v = p[v][i];
}
return p[u][0];
}
long long getDistance(int u, int v){
return D[u] + D[v] - 2 * D[LCA(u, v)];
}
void Init(int pN, int pA[], int pB[], int pD[]){
n = pN;
for (int i = 0; i < n - 1; i++){
int u = pA[i];
int v = pB[i];
int w = pD[i];
adj[u].push_back(ii(v, w));
adj[v].push_back(ii(u, w));
}
d[0] = 1;
DFS(0);
buildTree(0, -1, -1, 0);
for (int j = 1; j <= LOG; j++)
for (int i = 0; i < n; i++)
p[i][j] = p[p[i][j - 1]][j - 1];
}
inline void Update(int x){
int savex = x;
while (1){
if (t[x] != Time) {
f[x] = oo;
t[x] = Time;
}
f[x] = min(f[x], getDistance(savex, x));
int pp = par[x];
if (pp == -1) break;
x = pp;
}
}
long long Get(int x){
int savex = x;
long long res = oo;
while (1){
if (t[x] != Time){
f[x] = oo;
t[x] = Time;
}
res = min(res, getDistance(savex, x) + f[x]);
int pp = par[x];
if (pp == -1) break;
x = pp;
}
return res;
}
long long Query(int S, int X[], int T, int Y[]){
++Time;
for (int i = 0; i < S; i++)
Update(X[i]);
long long res = oo;
for (int i = 0; i < T; i++)
res = min(res, Get(Y[i]));
return res;
}
// int main(){
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
// read(n); read(q);
// for (int i = 1; i < n; i++){
// int u, v, w;
// read(u); read(v); read(w);
// adj[u].push_back(ii(v, w));
// adj[v].push_back(ii(u, w));
// }
// for (int i = 1; i <= q; i++){
// int S, T;
// read(S); read(T);
// for (int j = 0; j < S; j++)
// read(X[j]);
// for (int j = 0; j < T; j++)
// read(Y[j]);
// writeln(Query(S, X, T, Y));
// }
// }
