#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
#define pll pair<ll,ll>
#define fs first
#define sc second
#define ll long long
#define pii pair<int,int>
const int mxn = 1010;
vector<pair<ll,pii>> edges;
int dsu[mxn];
int root(int k){
return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
vector<pll> coords;
coords.push_back(make_pair(0ll,1));
coords.push_back(make_pair(get_distance(1,2),2));
pll pos = make_pair(0,coords.back().fs);
for(int i = 3;i<=N;i++){
ll ta = get_distance(1,i),tb = get_distance(2,i);
if(ta+tb == pos.sc-pos.fs)coords.push_back(make_pair(ta,i));
else if(ta<tb)coords.push_back(make_pair(-ta,i));
else coords.push_back(make_pair(tb+pos.sc,i));
}
sort(coords.begin(),coords.end());
for(int i = 1;i<N;i++){
A[i-1] = coords[i-1].sc;
B[i-1] = coords[i].sc;
W[i-1] = coords[i].fs-coords[i-1].fs;
}
return;
}
