#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include "citymapping.h"
const int nax = 5005;
int d[nax];
int d2[nax][nax];
vector<int> ch[nax];
int qry(int u, int v) {
if(d2[u][v] != -1) return d2[u][v];
d2[u][v] = d2[v][u] = get_distance(u, v);
return d2[u][v];
}
bool anc(int u, int v) {
if(u == 1) return 1;
return d[u] + qry(u, v) == d[v];
}
void find_roads(int n, int Q, int A[], int B[], int W[]) {
memset(d2, -1, sizeof(d2));
for(int i = 1; i <= n; i++) d2[i][i] = 0;
d[1] = 0;
for(int i = 2; i <= n; i++)
d[i] = qry(1, i);
vector<int> order(n - 1); iota(order.begin(), order.end(), 2);
sort(order.begin(), order.end(), [](int a, int b) {return d[a] < d[b];});
vector<int> path; path.reserve(n);
path.push_back(1);
int I = 0;
for(int &v : order) {
while(path.size() > 1 && !anc(path.back(), v)) path.pop_back();
while(1) {
int u = path.back();
bool dec = 0;
for(int &c : ch[u]) {
if(d[c] >= d[v]) continue;
if(anc(c, v)) {
path.push_back(c);
dec = 1;
break;
}
}
if(!dec) break;
}
int par = path.back();
int w = d[v] - d[par];
ch[par].push_back(v);
A[I] = par;
B[I] = v;
W[I++] = (int)w;
path.push_back(v);
}
}
