#include <bits/stdc++.h>
using namespace std;
#include "citymapping.h"
const int MAXN = 1000 + 10;
void find_roads(int N, int Q, int A[], int B[], int W[]) {
using TP = tuple<long long, int, int>;
priority_queue<TP, vector<TP>, greater<>> pq;
set<int> mk{1};
auto addEdge = [&](int x) {
for (int i = 1; i <= N; ++i) {
if (mk.count(i)) continue;
pq.push({get_distance(x, i), x, i});
}
};
addEdge(1);
int num = 0;
while (pq.size()) {
auto [w, a, b] = pq.top(); pq.pop();
if (mk.count(b)) continue;
mk.insert(b);
A[num] = a;
B[num] = b;
W[num] = w;
num += 1;
addEdge(b);
}
}
