#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void find_roads(int N, int Q, int A[], int B[], int W[]) {
vector<pair<ll , int>> v;
v.push_back({0LL , 1});
for (int i = 2;i <= N;i ++) {
ll w = get_distance(1 , i);
v.push_back({w , i});
}
sort(v.begin() , v.end());
int ind = 0;
for (int i = 1;i < N;i ++) {
if (ind == N - 1) {
break;
}
for (int j = i - 1;j >= 0;j --) {
ll w = v[i].first - v[j].first;
if (j >= 1) {
w = get_distance(v[i].second , v[j].second);
}
if (w == v[i].first - v[j].first) {
A[ind] = min(v[i].second , v[j].second);
B[ind] = max(v[i].second , v[j].second);
W[ind] = w;
ind ++;
break;
}
}
}
return;
}
/*
5 50000 5
1 4 8
2 4 1
3 4 7
3 5 3
*/
