#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};
int top = 0;
for (auto &vertex : ord)
{
for (int p = (int) deja.size() - 1; p >= 0; p--)
{
int oth = deja[p];
if (ask(oth, vertex) + dist0[oth] == dist0[vertex])
{
e_a[top] = oth + 1;
e_b[top] = vertex + 1;
e_w[top] = dist0[vertex] - dist0[oth];
top++;
break;
}
}
deja.push_back(vertex);
}
if (0)
{
for (int i = 0; i < top; i++)
{
cout << " : " << e_a[i] << " " << e_b[i] << " " << e_w[i] << "\n";
}
}
assert(top == n - 1);
return;
}
