#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++){
Edges mn = {-1,-1,(ll)1e9+7};
for(int j=i+1;j<=N;j++){
if(i==j)
continue;
if(get_distance(i,j) <= mn.w && find(i) != find(j)){
mn = {i,j,get_distance(i,j)};
}
}
if(mn.u == -1)
continue;
unite(mn.u,mn.v);
A[cur] = mn.u;
B[cur] = mn.v;
W[cur] = mn.w;
cur++;
}
return;
}
