#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e3+5;
ll dist[MAXN][MAXN];
vector<tuple<int, int, int> > ans;
vector<int> subtree[MAXN];
ll further[MAXN][2];
mt19937 rng(time(0));
int n;
ll query(int a, int b) {
if(a == b) return 0;
if(a > b) swap(a, b);
if(dist[a][b]) return dist[a][b];
// printf("query %d %d\n", a, b);
return dist[a][b] = get_distance(a, b);
}
void solve(int cur) {
if(subtree[cur].size() == 1) return;
int x = further[cur][0];
int y = x;
for(auto vertex : subtree[cur]) if(query(x, vertex) > query(x, y)) y = vertex;
// printf("solve %d >> %d %d\n", cur, x, y); for(auto vertex : subtree[cur]) printf("%d ", vertex); cout << endl;
vector<pair<ll, int> > line;
vector<pair<ll, int> > aux;
for(int vertex : subtree[cur]) {
ll val = query(x, vertex) + query(y, vertex) - query(x, y); val /= 2;
if(val == 0) line.push_back({query(x, vertex), vertex});
val = query(x, y) - query(vertex, y) + val;
aux.push_back({val, vertex});
}
sort(line.begin(), line.end());
sort(aux.begin(), aux.end());
subtree[cur].clear();
further[cur][0] = 0;
further[cur][1] = -1;
int p = 0;
for(int i = 0; i < line.size(); i++) {
int vertex = line[i].second;
ll dx = line[i].first;
while(p < aux.size() && aux[p].first == dx) {
ll val = query(x, aux[p].second) - dx;
if(val > further[vertex][1]) further[vertex][0] = aux[p].second, further[vertex][1] = val;
subtree[vertex].push_back(aux[p++].second);
}
if(i != 0) ans.push_back({vertex, line[i-1].second, line[i].first-line[i-1].first});
}
for(auto item : line) solve(item.second);
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
n = N;
int ori = rng()%n +1;
for(int i = 1; i <= n; i++) subtree[ori].push_back(i);
for(int i = 1; i <= n; i++) if(query(ori, i) > further[ori][1]) further[ori][0] = i, further[ori][1] = query(ori, i);
solve(ori);
for(int i = 0; i < ans.size(); i++) tie(A[i], B[i], W[i]) = ans[i];
}
