#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ask(int i, int j)
{
return get_distance(i + 1, j + 1);
}
void find_roads(int n, int q, int e_a[], int e_b[], int e_w[])
{
vector<ll> dist0(n, 0);
vector<int> ord;
for (int i = 1; i < n; i++)
{
dist0[i] = ask(0, i);
ord.push_back(i);
}
sort(ord.begin(), ord.end(), [&] (int i, int j) {return dist0[i] < dist0[j];});
vector<int> deja = {0};
vector<vector<int>> g;
int top = 0;
auto add_edge = [&] (int a, int b)
{
e_a[top] = a + 1;
e_b[top] = b + 1;
e_w[top] = dist0[b] - dist0[a];
top++;
};
for (auto &vertex : ord)
{
///dfs(0);
for (int p = (int) deja.size() - 1; p >= 0; p--)
{
int oth = deja[p];
if (ask(oth, vertex) + dist0[oth] == dist0[vertex])
{
add_edge(oth, vertex);
break;
}
}
deja.push_back(vertex);
}
assert(top == n - 1);
}
