#include <bits/stdc++.h>
#include "citymapping.h"
using namespace std;
#define MOD 1000000007
#define fir first
#define sec second
#define pushf push_front
#define pushb push_back
#define popf pop_front
#define popb pop_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define FOR(i, s, e) for(int i = s; i < e; i++)
#define RFOR(i, s, e) for(int i = e-1; i >= s; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef deque<int> dqi;
typedef deque<ll> dqll;
typedef deque<pii> dqpii;
typedef deque<pll> dqpll;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pqll;
typedef priority_queue<pii> pqpii;
typedef priority_queue<pll> pqpll;
typedef priority_queue<int, vi, greater<int> > r_pqi;
typedef priority_queue<ll, vll, greater<ll> > r_pqll;
typedef priority_queue<pii, vpii, greater<pii> > r_pqpii;
typedef priority_queue<pll, vpll, greater<pll> > r_pqpll;
const int N = 1e3 + 5;
ll d[N][N];
bool del[N];
int sz[N], heavy[N];
vi adj[N];
ll dist(int x, int y) {
if (x == y) {
return 0;
}
if (x > y) {
swap(x, y);
}
if (!d[x][y]) {
d[x][y] = get_distance(x, y);
}
return d[x][y];
}
void dfs(int u) {
sz[u] = 1, heavy[u] = 0;
for (int v : adj[u]) if (!del[v]){
dfs(v);
sz[u] += sz[v];
if (sz[v] > sz[heavy[u]]) {
heavy[u] = v;
}
}
}
void find_roads(int n, int q, int a[], int b[], int w[]){
vi sr;
for (int i = 2; i < n + 1; ++ i) sr.pushb(i);
sort(all(sr), [&](int u, int v){
return dist(1, u) < dist(1, v);
});
int cnt = 0;
for (int u : sr) {
int r = 1;
for (int i = 1; i <= n; ++ i) del[i] = 0;
while (true){
dfs(r); vi path = {r};
while (heavy[r]) r = heavy[r], path.pushb(r);
if (path.size() == 1) break;
ll x = dist(1, path.back()) + dist(1, u) - dist(u, path.back()); x /= 2;
for (int u : path) if (dist(1, u) == x) {
r = u; //break;
} else del[u] = 1;
}
adj[r].pushb(u);
a[cnt] = r, b[cnt] = u, w[cnt] = d[1][u] - d[1][r];
++cnt;
}
}
