#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
vector<int> e;
void init(int n){
e = vector<int>(n, -1);
}
int get(int x){
return (e[x] < 0 ? x : e[x] = get(e[x]));
}
bool same_set(int x, int y){
return get(x) == get(y);
}
bool unite(int x, int y){
x = get(x), y = get(y);
if(e[x] < e[y])
swap(x, y);
e[x] += e[y];
e[y] = x;
return true;
}
};
void find_roads(int N, int Q, int A[], int B[], int W[]) {
vector<pair<pair<int, int>, long long>> edges((N*(N-1))/2);
int c = 0;
for(int i = 1; i <= N; i++)
for(int j = i+1; j <= N; j++)
edges[c++] = {{i, j}, get_distance(i, j)};
sort(edges.begin(), edges.end(), [&](pair<pair<int, int>, long long> &a, pair<pair<int, int>, long long> &b){
if(a.second < b.second) return true;
return false;
});
DSU s;
s.init(N);
int m = 0;
for(int i = 0; i < c; i++){
if(s.same_set(edges[i].first.first, edges[i].first.second)) continue;
s.unite(edges[i].first.first, edges[i].first.second);
A[m] = edges[i].first.first, B[m] = edges[i].first.second, W[m] = edges[i].second;
m++;
}
return;
}
