#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
void find_roads(int n, int Q, int A[], int B[], int W[]) {
ll cnt = 1;
vector<pair<ll,ll>> arr;
for (int i = 2; i <= n; ++i) {
ll d = get_distance(1, i);
arr.pb({d, i});
}
sort(arr.begin(), arr.end());
A[0]=1;
B[0]=arr[0].se;
W[0]=arr[0].fi;
ll ptr1=1,ptr2=arr[0].se;
for (int i = 1; i < n-1; ++i) {
ll x=arr[i].se;
ll d1= get_distance(ptr1,x);
ll d2= get_distance(ptr2,x);
if (d1<d2){
A[cnt]=ptr1;
B[cnt]=x;
W[cnt]=d1;
ptr1=x;
cnt++;
}
else{
A[cnt]=ptr2;
B[cnt]=x;
W[cnt]=d2;
ptr2=x;
cnt++;
}
}
// for (int i = 0; i < n - 1; ++i) {
// cout << A[i] << ' ' << B[i] << ' ' << W[i] << endl;
// }
}
