#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
struct unionFind{
int par[MAXN], size[MAXN];
unionFind(){
for (int i = 0; i < MAXN; i++)
par[i] = i, size[i] = 1;
}
int find(int x){ return (x == par[x]) ? x : (par[x] = find(par[x])); }
bool same(int a, int b) { return find(a) == find(b) ; }
void unite(int a, int b) {
a = find(a), b = find(b);
if (size[a] < size[b]) swap(a, b);
par[b] = a, size[a] += size[b];
}
};
#define we(i) get<0>(i)
#define u(i) get<1>(i)
#define v(i) get<2>(i)
void find_roads(int n, int q, int a[], int b[], int w[]) {
vector<tuple<int, int, int>> k; // w, a, b
unionFind uf;
for (int i = 1; i < n; i++)
for (int j = i + 1; j <= n; j++)
k.push_back({get_distance(i, j), i, j});
sort(k.begin(), k.end());
int ind = 0;
for (auto x : k){
int s = we(x), i = u(x), j = v(x);
if (!uf.same(i, j))
a[ind] = i, b[ind] = j, w[ind] = s, ind++, uf.unite(i, j);
}
}
