#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
void find_roads(int n, int q, int a[], int b[], int w[]) {
vector<array<long long,2>>g[n];
for(int i = 0;i<n;i++){
for(int j = i+1;j<n;j++){
long long dist = get_distance(i+1,j+1);
g[i].push_back({j,dist});
g[j].push_back({i,dist});
}
}
priority_queue<array<long long,3>,vector<array<long long,3>>,greater<array<long long,3>>>pq;
bool vis[n];
fill(vis,vis+n,0);
for(array<long long,2>e:g[0]){
//cout << "pushed1: " << e[1] << " " << 0 << " " << e[0] << endl;
pq.push({e[1],0,e[0]});
}
vis[0]=1;
int ind = 0;
while(!pq.empty()){
array<long long,3>e = pq.top();
pq.pop();
if(vis[e[2]])
continue;
vis[e[2]]=1;
cout << e[1] << " " << e[2] << " " << e[0] << endl;
a[ind]=e[1]+1;
b[ind]=e[2]+1;
w[ind]=e[0];
ind++;
for(array<long long,2>a:g[e[2]]){
//cout << "pushed2: " << a[1] << " " << e[2] << " " << a[1] << endl;
pq.push({a[1],e[2],a[0]});
}
}
return;
}
