#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3+3;
mt19937 rng(time(nullptr) + 69);
int n, nd[N], deg[N];
pair<int, int> p[N], d[N];
void find_roads(signed N, signed Q, signed A[], signed B[], signed W[]) {
n = N;
for (int i = 0; i < n; i++) {
nd[i] = i+1;
deg[i] = 0;
}
shuffle(nd, nd+n, rng);
d[0] = make_pair(0, nd[0]);
for (int i = 1; i < n; i++) {
d[i] = make_pair(get_distance(nd[0], nd[i]), nd[i]);
}
sort(d, d+n);
set<int> st;
for (int i = 1; i < n; i++) {
int mn = d[i].first;
int best = nd[0];
for (int j : st) {
if (mn == 1) break;
int x = get_distance(j, d[i].second);
if (x < mn) {
mn = x;
best = j;
}
}
p[d[i].second] = make_pair(best, mn);
if (++deg[best] == 3) {
st.erase(best);
}
st.insert(d[i].second);
}
for (int i = 1; i < N; i++) {
A[i] = p[nd[i]].first;
B[i] = nd[i];
W[i] = p[nd[i]].second;
}
return;
}
