#include "factories.h"
#define pii pair<ll, ll>
#define fi first
#define se second
#define ll long long
#include <bits/stdc++.h>
using namespace std;
const ll M = 5e3+3, R=1e17;
int n;
vector<pii> graf[M];
ll dist[M][M];
void dijkstra(int v)
{
for(int i=0; i<n; i++) dist[v][i] = R;
priority_queue<pii, vector<pii>, greater<pii>> pq;
dist[v][v] = 0;
pq.push({0, v});
bool vis[n]{};
while(!pq.empty())
{
pii p = pq.top(); pq.pop();
if(vis[p.se]) continue;
vis[p.se] = 1;
for(auto x: graf[p.se])
if(x.se + x.fi < dist[v][x.fi])
{
dist[v][x.fi] = x.se + p.fi;
pq.push({dist[v][x.fi], x.fi});
}
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i=0; i<N; i++)
graf[A[i]].push_back({B[i], D[i]}),
graf[B[i]].push_back({A[i], D[i]});
for(int i=0; i<N; i++)
dijkstra(i);
}
long long Query(int S, int X[], int T, int Y[]) {
ll mn = R;
for(int i=0; i<S; i++)
for(int j=0; j<T; j++)
mn = min(mn, dist[X[i]][Y[j]]);
return mn;
}
