#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define all(v) v.begin(),v.end()
#define mk make_pair
#define pb push_back
#define eb emplace_back
typedef pair<ll,ll> pii;
const int maxn = 5e5 + 10;
vector<pii> adj[maxn];
int in[maxn],out[maxn],t,p[maxn][20];
ll d[maxn];
void dfs(int i,int pa)
{
in[i] = ++t;
p[i][0] = pa;
for(int j = 1;j<20;j++)p[i][j] = p[p[i][j-1]][j-1];
for(pii k :adj[i])
{
if(k.fi==pa)continue;
d[k.fi] = d[i] + k.se;
dfs(k.fi,i);
}
out[i] = t;
}
int lca(int u,int v)
{
if(in[u] > in[v])swap(u,v);
if(u==v)return u;
for(int j = 19;j>=0;j--)
{
if(p[v][j] && in[p[v][j]] > in[u])v = p[v][j];
}
return p[v][0];
}
bool cmp(int &i,int &j)
{
return in[i]<in[j];
}
void Init(int N, int A[], int B[], int D[]) {
for(int i =0;i<N-1;i++)
{
A[i]++;
B[i]++;
adj[A[i]].pb(mk(B[i],D[i]));
adj[B[i]].pb(mk(A[i],D[i]));
}
dfs(1,0);
}
bool c[maxn];
void filter(vector<int> & v)
{
sort(all(v),cmp);
v.resize(unique(all(v))-v.begin());
}
vector<pii> com_adj[maxn];
priority_queue<pii,vector<pii>,greater<pii>>q;
ll dp[maxn];
long long Query(int S, int X[], int T, int Y[]) {
vector<int> v;
for(int i = 0;i<S;i++)
{
X[i]++;
v.pb(X[i]);
q.push(mk(0,X[i]));
}
for(int i = 0;i<T;i++)
{
Y[i]++;
c[Y[i]]=1;
v.pb(Y[i]);
}
filter(v);
int n = v.size();
for(int i = 1;i<n;i++)
{
v.pb(lca(v[i],v[i-1]));
}
filter(v);
stack<int> st;
for(int k : v)
{
while(st.size()&&out[st.top()]<out[k])st.pop();
if(st.size())
{
int p = st.top();
com_adj[k].pb(mk(p,d[k] - d[p]));
com_adj[p].pb(mk(k,d[k] - d[p]));
// cout<<p<<' '<<k<<' '<<d[k]-d[p]<<'\n';
}
st.push(k);
dp[k] = LLONG_MAX;
// cout<<k<<' '<<in[k]<<' '<<out[k]<<'\n';;
}
for(int i = 0;i<S;i++)
{
dp[X[i]] = 0;
}
ll ans = LLONG_MAX;
while(q.size())
{
ll w = q.top().fi;
int i = q.top().se;
q.pop();
if(w != dp[i])continue;
// cout<<i<<' '<<w<<'\n';
if(c[i])
{
ans = w;
break;
}
for(pii k : com_adj[i])
{
if(dp[k.fi] > w + k.se)
{
q.push(mk(dp[k.fi] = w + k.se,k.fi));
}
}
}
for(int k : v)
{
c[k]=0;
com_adj[k].clear();
}
return ans;
}
// int main()
// {
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// int n,t;
// cin>>n>>t;
// int u[n-1],v[n-1],w[n-1];
// for(int i = 0;i<n-1;i++)
// {
// cin>>u[i]>>v[i]>>w[i];
// }
// Init(n,u,v,w);
// while(t--)
// {
// int n,m;
// cin>>n>>m;
// int u[n],v[m];
// for(int i = 0;i<n;i++)
// cin>>u[i];
// for(int i = 0;i<m;i++)
// cin>>v[i];
// cout<<Query(n,u,m,v)<<'\n';
// }
// return 0;
// }
