#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
// inline void setup()
// {
// #ifndef ONLINE_JUDGE
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
// #endif
// }
int sz[500000], last_centroid[500000], depth[500000], pre[20][500000];
long long dist[500000], nearest[500000], temp;
bool check[500000];
vector<pair<int, int>> g[500000];
inline void CalculateSize(int node, int par)
{
sz[node] = 1;
for (auto &i : g[node])
{
if (i.first != par && !check[i.first])
{
CalculateSize(i.first, node);
sz[node] += sz[i.first];
}
}
}
inline int GetCentroid(int node, int par, int root)
{
for (auto &i : g[node])
{
if (i.first != par && !check[i.first] && sz[i.first] * 2 > sz[root])
{
return GetCentroid(i.first, node, root);
}
}
return node;
}
inline void FindCentroid(int node, int LastCentroid)
{
int centroid;
CalculateSize(node, node);
centroid = GetCentroid(node, node, node);
last_centroid[centroid] = LastCentroid;
check[centroid] = true;
for (auto &i : g[centroid])
{
if (!check[i.first])
{
FindCentroid(i.first, centroid);
}
}
}
inline void FormLCA(int node, int par)
{
pre[0][node] = par;
for (int i = 1; i < 20; ++i)
{
pre[i][node] = pre[i - 1][pre[i - 1][node]];
}
for (auto &i : g[node])
{
if (i.first != par)
{
depth[i.first] = depth[node] + 1;
dist[i.first] = dist[node] + i.second;
FormLCA(i.first, node);
}
}
}
inline int LCA(int ina, int inb)
{
if (depth[ina] != depth[inb])
{
if (depth[ina] < depth[inb])
{
swap(ina, inb);
}
for (int i = 19; i >= 0; --i)
{
if (depth[pre[i][ina]] >= depth[inb])
{
ina = pre[i][ina];
}
}
}
if (ina == inb)
{
return ina;
}
for (int i = 19; i >= 0; --i)
{
if (pre[i][ina] != pre[i][inb])
{
ina = pre[i][ina];
inb = pre[i][inb];
}
}
return pre[0][ina];
}
inline long long Dist(int ina, int inb)
{
return dist[ina] + dist[inb] - 2 * dist[LCA(ina, inb)];
}
inline void Update(int node)
{
int cur = node;
while (cur != -1)
{
temp = Dist(cur, node);
nearest[cur] = (nearest[cur] == -1 ? temp : min(temp, nearest[cur]));
cur = last_centroid[cur];
}
}
inline void Reset(int node)
{
int cur = node;
while (cur != -1)
{
nearest[cur] = -1;
cur = last_centroid[cur];
}
}
inline long long Get(int node)
{
long long res = -1;
int cur = node;
while (cur != -1)
{
if (nearest[cur] != -1)
{
temp = Dist(cur, node) + nearest[cur];
res = (res == -1 ? temp : min(temp, res));
}
cur = last_centroid[cur];
}
return res;
}
long long Query(int S, int X[], int T, int Y[])
{
long long res = 1e18;
for (int i = 0; i < S; ++i)
{
Update(X[i]);
}
for (int i = 0; i < T; ++i)
{
res = min(res, Get(Y[i]));
}
for (int i = 0; i < S; ++i)
{
Reset(X[i]);
}
return res;
}
void Init(int N, int A[], int B[], int D[])
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
fill_n(nearest, N, -1);
for (int i = 0; i < N - 1; ++i)
{
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
depth[0] = dist[0] = 0;
FindCentroid(0, -1);
FormLCA(0, 0);
}
// int main()
// {
// setup();
// int n, q, s, t;
// cin >> n >> q;
// int A[n], B[n], D[n];
// for (int i = 0; i < n - 1; ++i)
// {
// cin >> A[i] >> B[i] >> D[i];
// }
// Init(n, A, B, D);
// while (q--)
// {
// cin >> s >> t;
// for (int i = 0; i < s; ++i)
// {
// cin >> A[i];
// }
// for (int i = 0; i < t; ++i)
// {
// cin >> B[i];
// }
// cout << Query(s, A, t, B) << "\n";
// }
// return 0;
// }
