#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<pair<int, int> > g[MAXN];
int sz[MAXN];
ll depth[MAXN];
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];
return dist[a][b] = get_distance(a, b);
}
bool cmp(pair<int, ll> a, pair<int, ll> b) {
return sz[a.first] > sz[b.first];
}
void predfs(int cur) {
sz[cur] = 1;
for(auto edge : g[cur]) {
int viz, w; tie(viz, w) = edge;
depth[viz] = depth[cur]+w;
predfs(viz);
sz[cur] += sz[viz];
}
sort(g[cur].begin(), g[cur].end(), cmp);
}
ll dfs(int cur, int x) {
// printf("%d %d\n", cur, x);
if(g[cur].empty()) {
ll val = query(1, x)+query(x, cur)-query(1, cur);
val /= 2;
val = query(1, x)-val;
if(val == depth[cur]) {
g[cur].push_back({x, query(cur, x)});
ans.push_back({cur, x, query(cur, x)});
// printf("added %d %d %lld\n", cur, x, query(cur, x));
return -1;
}
return val;
}
bool explore = 0;
for(auto edge : g[cur]) {
int viz, w; tie(viz, w) = edge;
ll val = dfs(viz, x);
if(val < depth[cur]) return val;
}
}
void process(int cur) {
predfs(1);
dfs(1, cur);
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
n = N;
vector<pair<ll, int> > aux;
for(int i = 1; i <= n; i++) aux.push_back({query(1, i), i});
sort(aux.begin(), aux.end());
for(auto item : aux) if(item.second != 1) process(item.second);
for(int i = 0; i < ans.size(); i++) tie(A[i], B[i], W[i]) = ans[i];
}
