#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define fi first
#define se second
#define pb push_back
vector<ll> p;
vector<ll> sz;
ll find(ll x) {
while (x != p[x]) x = p[x];
return x;
}
void unite(ll a, ll b) {
a = find(a);
b = find(b);
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
void find_roads(int n, int Q, int A[], int B[], int W[]) {
ll cnt = 0;
p.resize(n);
sz.assign(n, 1);
for (int i = 0; i < n; ++i) {
p[i] = i;
}
vector<vector<ll>> lst;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
ll d = get_distance(i, j);
lst.pb({d, i, j});
}
}
sort(lst.begin(), lst.end());
// for(auto &elt : lst){
// cout << elt[0] << ' ' << elt[1] << ' ' << elt[2] << endl;
// }
for (auto &elt: lst) {
ll a = elt[1] - 1, b = elt[2] - 1, w = elt[0];
if (find(a) != find(b)) {
unite(a, b);
A[cnt] = a + 1;
B[cnt] = b + 1;
W[cnt] = w;
cnt++;
// cout << a + 1 << ' ' << b + 1 << ' ' << w << endl;
}
}
}
