#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
/*
void openFiles() {
#ifdef KEK
assert(freopen("input.txt", "r", stdin));
assert(freopen("output.txt", "w", stdout));
#endif
}
*/
void IOoptimize() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int MAXN = 5e3 + 10;
const ll INF = 1e17;
vector<pair<int, ll>> g[MAXN];
int n;
//int type[MAXN];
ll dist[MAXN][MAXN];
bool used[MAXN];
void dfs(int u, int w) {
used[u] = true;
for (auto v : g[u]) {
if (!used[v.first]) {
dist[w][v.first] = dist[w][u] + v.second;
dfs(v.first, w);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
IOoptimize();
n = N;
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]});
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = INF;
}
}
for (int i = 0; i < n; i++) {
dist[i][i] = 0;
}
for (int i = 0; i < n; i++) {
memset(used, 0, sizeof(used));
dfs(i, i);
}
}
long long Query(int S, int X[], int T, int Y[]) {
//memset(type, 0, sizeof(type));
/*for (int i = 0; i < S; i++) {
type[X[i]] = 1;
}
for (int i = 0; i < T; i++) {
type[Y[i]] = -1;
}*/
ll ans = INF;
for (int i = 0; i < S; i++) {
for (int j = 0; j < T; j++) {
ans = min(ans, dist[X[i]][Y[j]]);
}
}
return ans;
}
