#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ll inf = 1e17;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi = 3.14159265359;
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 5e5 + 5;
#include "factories.h"
vector<pii> g[mxn];
int sub[mxn];
bool deleted[mxn];
int n;
int sparse[mxn][20];
ll dist[mxn];
int depth[mxn];
void dfs0(int u, int p){
sub[u] = 1;
for(auto e : g[u]){
if(e.st == p || deleted[e.st]) continue;
dfs0(e.st, u);
sub[u] += sub[e.st];
}
}
int dfs1(int u, int p){
for(auto e : g[u]){
if(e.st != p && !deleted[e.st] && sub[e.st] > n / 2){
return dfs1(e.st, u);
}
}
return u;
}
void prep(int u, int p){
sparse[u][0] = p;
fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i - 1]][i - 1];
for(auto e : g[u]){
if(e.st == p) continue;
dist[e.st] = dist[u] + e.nd;
depth[e.st] = depth[u] + 1;
prep(e.st, u);
}
}
int lca(int a, int b){
int d = min(depth[a], depth[b]);
for(int i = 19; i >= 0; i --){
if(depth[sparse[a][i]] >= d) a = sparse[a][i];
if(depth[sparse[b][i]] >= d) b = sparse[b][i];
}
if(a == b){
return a;
}
for(int i = 19; i >= 0; i --){
if(sparse[a][i] != sparse[b][i]){
a = sparse[a][i];
b = sparse[b][i];
}
}
return sparse[a][0];
}
ll distintree(int a, int b){
int k = lca(a, b);
return dist[a] + dist[b] - 2 * dist[k];
}
int parent[mxn];
ll opt[mxn];
void decompose(int root, int p){
dfs0(root, root);
n = sub[root];
int centroid = dfs1(root, root);
opt[centroid] = inf;
if(root != p) parent[centroid] = p;
else parent[centroid] = centroid;
deleted[centroid] = true;
for(auto u : g[centroid]){
if(deleted[u.st]) continue;
decompose(u.st, centroid);
}
}
void Init(int N, int A[], int B[], int D[]) {
fr(i, 0, N - 1){
g[A[i]].pb({B[i], D[i]});
g[B[i]].pb({A[i], D[i]});
}
decompose(0, 0);
prep(0, 0);
}
void update(int u){
opt[u] = 0;
int x = u;
while(parent[x] != x){
x = parent[x];
opt[x] = min(opt[x], distintree(x, u));
}
}
void rupdate(int u){
opt[u] = inf;
int x = u;
while(parent[x] != x){
x = parent[x];
opt[x] = inf;
}
}
ll query(int u){
ll ret = opt[u];
int x = u;
while(parent[x] != x){
x = parent[x];
ret = min(ret, opt[x] + distintree(x, u));
}
return ret;
}
ll Query(int S, int X[], int T, int Y[]) {
fr(i, 0, S){
update(X[i]);
}
ll ret = inf;
fr(i, 0, T){
ret = min(ret, query(Y[i]));
}
fr(i, 0, S){
rupdate(X[i]);
}
return ret;
}/*
int main(){
int N, Q;
cin >> N >> Q;
int A[N], B[N], D[N];
fr(i, 0, N - 1){
cin >> A[i] >> B[i] >> D[i];
}
Init(N, A, B, D);
fr(i, 0, Q){
int S, T;
cin >> S >> T;
int X[S], Y[T];
fr(j, 0, S){
cin >> X[j];
}
fr(j, 0, T){
cin >> Y[j];
}
cout << Query(S, X, T, Y)<<endl;
}
*/
