#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
#define pll pair<ll,ll>
#define fs first
#define sc second
#define ll long long
#define pii pair<int,int>
const int mxn = 1010;
vector<pair<ll,pii>> edges;
int dsu[mxn];
int root(int k){
return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
for(int i = 1;i<=N;i++){
for(int j = i+1;j<=N;j++){
edges.push_back(make_pair(get_distance(i,j),make_pair(i,j)));
}
}
for(int i = 1;i<=N;i++)dsu[i] = i;
sort(edges.begin(),edges.end());
int pt = 0;
for(auto &i:edges){
int a = i.sc.fs,b = i.sc.sc;
if(root(a) == root(b))continue;
A[pt] = a,B[pt] = b,W[pt] = i.fs;
dsu[root(a)] = root(b);
pt++;
}
return;
}
