#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct Edges{
int u,v;
ll w;
bool operator<(const Edges& e)const{
return w < e.w;
}
};
vector<int> parent;
int find(int node){
if(parent[node]==node)
return node;
return parent[node] = find(node);
}
void unite(int a,int b){
a = find(a),b = find(b);
parent[b] = a;
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
parent.resize(N+1);
for(int i=1;i<=N;i++)
parent[i] = i;
int cur = 0;
for(int i=1;i<=N;i++){
vector<Edges> edges;
for(int j=i+1;j<=N;j++){
if(i==j)
continue;
edges.push_back({i,j,get_distance(i,j)});
}
sort(edges.begin(),edges.end());
if(find(edges[0].u) != find(edges[0].v)){
unite(edges[0].u,edges[0].v);
A[cur] = edges[0].u;
B[cur] = edges[0].v;
W[cur] = edges[0].w;
cur++;
}
}
return;
}
