#include<bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define ll long long
using namespace std;
typedef pair<int,int> pii;

struct point{
    int x,y,w;

    point(){}
    point(int x,int y,int w){
        this->x=x;
        this->y=y;
        this->w=w;
    }
};



namespace emst_namespace{

/**
 * Disjoint-set-union data structure
 */
class DSU {

public:

    explicit DSU(size_t n = 0);

    size_t get_set(size_t x) const;
    bool is_in_same_set(size_t x, size_t y) const;

    void reset(size_t n);
    bool unite(size_t x, size_t y);

private:

    mutable std::vector<size_t> p;
    std::vector<size_t> rank;
};


DSU::DSU(size_t n) {
    reset(n);
}

size_t DSU::get_set(size_t x) const {
    return p[x] == x ? x : p[x] = get_set(p[x]);
}

bool DSU::is_in_same_set(size_t x, size_t y) const {
    return get_set(x) == get_set(y);
}

void DSU::reset(size_t n) {
    p.resize(n);
    rank.assign(n, 0);
    for (size_t i = 0; i < n; i++) {
        p[i] = i;
    }
}

bool DSU::unite(size_t x, size_t y) {
    size_t set_a = get_set(x);
    size_t set_b = get_set(y);
    if (set_a == set_b) {
        return false;
    }
    if (rank[set_a] > rank[set_b]) {
        std::swap(set_a, set_b);
    }
    if (rank[set_a] == rank[set_b]) {
        rank[set_b]++;
    }
    p[set_a] = set_b;
    return true;
}

/// DSU END



/**
 * Point in DIM-dimensional space
 */
template<size_t DIM>
class Point {

public:
    Point();

    const double & operator[](size_t i) const;
    double & operator[](size_t i);

    /**
     * Distance between two points
     */
    template<size_t DIM_>
    friend double distance(const Point<DIM_> & a, const Point<DIM_> & b);

private:
    double data[DIM];
};

/**
 * Point with id
 */
template<size_t DIM>
class UPoint : public Point<DIM> {
public:

    UPoint(const Point<DIM> & ref, size_t id = 0);
    UPoint(size_t id = 0);

    size_t get_id() const;

private:
    size_t id;
};

/**
 * Bounding box in DIM-dimensional space
 */
template<size_t DIM>
class AABB {
public:
    AABB();
    /**
     * Construct bounding box from vector iterator
     */
    AABB(typename std::vector<UPoint<DIM>>::const_iterator iter, typename std::vector<UPoint<DIM>>::const_iterator end);

    /**
     * Size of the k-th dimension
     */
    double size(size_t k) const;

    /**
     * Get the index of a dimension with the largest size
     */
    size_t get_largest_dim() const;

    /**
     * Distance between two bounding boxes
     */
    template<size_t DIM_>
    friend double distance(const AABB<DIM_> & a, const AABB<DIM_> & b);

private:
    Point<DIM> minimal;
    Point<DIM> maximal;
};

// Implementation

template<size_t DIM>
Point<DIM>::Point() {
    std::fill(data, data + DIM, 0.0);
}

template<size_t DIM>
const double & Point<DIM>::operator[](size_t i) const {
    return data[i];
}

template<size_t DIM>
double &  Point<DIM>::operator[](size_t i) {
    return data[i];
}

template<size_t DIM>
UPoint<DIM>::UPoint(const Point<DIM> & ref, size_t id) : Point<DIM>(ref), id(id) {}

template<size_t DIM>
UPoint<DIM>::UPoint(size_t id) :id(id) {}

template<size_t DIM>
size_t UPoint<DIM>::get_id() const {
    return id;
}

template<size_t DIM>
AABB<DIM>::AABB() {}

template<size_t DIM>
AABB<DIM>::AABB(typename std::vector<UPoint<DIM>>::const_iterator iter, typename std::vector<UPoint<DIM>>::const_iterator end) {
    minimal = maximal = *iter;
    for (; iter != end; ++iter) {
        for (size_t k = 0; k < DIM; k++) {
            minimal[k] = std::min(minimal[k], (*iter)[k]);
            maximal[k] = std::max(maximal[k], (*iter)[k]);
        }
    }
}

template<size_t DIM>
double AABB<DIM>::size(size_t k) const {
    return maximal[k] - minimal[k];
}

template<size_t DIM>
size_t AABB<DIM>::get_largest_dim() const {
    size_t biggest_dim = 0;
    for (size_t k = 1; k < DIM; k++) {
        if (size(k) > size(biggest_dim))
            biggest_dim = k;
    }
    return biggest_dim;
}

template<size_t DIM>
double distance(const Point<DIM> & a, const Point<DIM> & b) {
    double distance_sqr = 0;
    for (size_t k = 0; k < DIM; k++) {
        double diff = a[k] - b[k];
        distance_sqr += diff * diff;
    }
    return sqrt(distance_sqr);
}

template<size_t DIM>
double distance(const AABB<DIM> & a, const AABB<DIM> & b) {
    double distance_sqr = 0;
    for (size_t k = 0; k < DIM; k++) {
        double diff = std::max(a.minimal[k], b.minimal[k]) - std::min(a.maximal[k], b.maximal[k]);
        if (diff > 0) {
            distance_sqr += diff * diff;
        }
    }
    return sqrt(distance_sqr);
}

///Points done



/**
 * K-d tree data structure
 */
template<size_t DIM>
struct KdTree {
public:
    KdTree();
    /**
     * Construct K-d tree with height at most max_height from a given set of points
     */
    KdTree(const std::vector<Point<DIM>> & points, size_t max_height);

    size_t get_root_id() const;
    size_t get_maximal_id() const;
    size_t get_left_child_id(size_t id) const;
    size_t get_right_child_id(size_t id) const;
    const AABB<DIM> & get_bounding_box(size_t id) const;
    bool is_leaf(size_t id) const;

    typename std::vector<UPoint<DIM>>::const_iterator points_begin(size_t node_id) const;
    typename std::vector<UPoint<DIM>>::const_iterator points_end(size_t node_id) const;

private:
    /**
     * K-d tree node. Represents part of space with points from (start) to (start+size-1) position in points array
     */
    struct KdNode {
        KdNode() : start(0), is_leaf(false), size(0) {}
        AABB<DIM> aabb;
        bool is_leaf; //is this node a leaf node and has no childs
        size_t start;
        size_t size;
    };
    /**
     * Recursively build tree for current node node_id, for points from position (start) to position (start+size-1)
     */
    void build(size_t node_id, size_t start, size_t size, size_t remaining_height);

    std::vector<UPoint<DIM>> points;
    std::vector<KdNode> nodes;
};

// Implementation

template<size_t DIM>
KdTree<DIM>::KdTree() {}

template<size_t DIM>
KdTree<DIM>::KdTree(const std::vector<Point<DIM>> & points, size_t max_height) {
    this->points.reserve(points.size());
    for (auto & p : points) {
        this->points.push_back(UPoint<DIM>(p, this->points.size()));
    }
    nodes.resize(points.size() * 4);
    build(1, 0, points.size(), max_height);
}

template<size_t DIM>
size_t KdTree<DIM>::get_root_id() const {
    return 1;
}

template<size_t DIM>
size_t KdTree<DIM>::get_maximal_id() const {
    return (nodes.empty() ? 0 : nodes.size() - 1);
}

template<size_t DIM>
size_t KdTree<DIM>::get_left_child_id(size_t id) const {
    return id * 2;
}

template<size_t DIM>
size_t KdTree<DIM>::get_right_child_id(size_t id) const {
    return id * 2 + 1;
}


template<size_t DIM>
bool KdTree<DIM>::is_leaf(size_t id) const {
    return nodes[id].is_leaf;
}

template<size_t DIM>
const AABB<DIM> & KdTree<DIM>::get_bounding_box(size_t id) const {
    return nodes[id].aabb;
}

template<size_t DIM>
typename std::vector<UPoint<DIM>>::const_iterator KdTree<DIM>::points_begin(size_t node_id) const {
    return points.begin() + nodes[node_id].start;
}

template<size_t DIM>
typename std::vector<UPoint<DIM>>::const_iterator KdTree<DIM>::points_end(size_t node_id) const {
    return points.begin() + nodes[node_id].start + nodes[node_id].size;
}

template<size_t DIM>
void KdTree<DIM>::build(size_t node_id, size_t start, size_t size, size_t remaining_height) {
    nodes[node_id].aabb = AABB<DIM>(points.cbegin() + start, points.cbegin() + start + size);
    nodes[node_id].start = start;
    nodes[node_id].size = size;

    if (size == 1 || remaining_height == 0) {
        nodes[node_id].is_leaf = true;
        return;
    }

    size_t biggest = nodes[node_id].aabb.get_largest_dim();

    std::nth_element(points.begin() + start, points.begin() + start + size / 2, points.begin() + start + size,
        [&biggest](const Point<DIM> & a, const Point<DIM> & b) {
        return a[biggest] < b[biggest];
    });

    // recursively call build for two parts
    build(node_id * 2, start, size / 2, remaining_height - 1);
    build(node_id * 2 + 1, start + size / 2, (size + 1) / 2, remaining_height - 1);
}

/// kd tree done


typedef std::pair<size_t, size_t> Edge;

template<size_t DIM>
class EmstSolver {
public:
    EmstSolver() = default;

    const std::vector<Edge> & get_solution() const { return solution; }
    const double & get_total_length() const { return total_length; }

protected:
    std::vector<Edge> solution;
    double total_length = 0.0;
};

/**
 * Implementation of EMST algorithm using K-d tree
 * "Fast Euclidean Minimum Spanning Tree: Algorithm, Analysis, and Applications. William B. March, Parikshit Ram, Alexander G. Gray"
 * Time complexity: O(cNlogN), extra constant c depends on the distribution of points
 */
template<size_t DIM>
class KdTreeSolver : public EmstSolver<DIM> {
public:
    explicit KdTreeSolver(const std::vector<Point<DIM>> & points) :num_points(points.size()) {
        dsu.reset(num_points);
        tree = KdTree<DIM>(points, static_cast<size_t>(floor(log2(num_points)) - 1));
        is_fully_connected.assign(tree.get_maximal_id() + 1, false);
        solve();
        // todo: clear containers
    }

private:
    void solve() {
        auto & solution = EmstSolver<DIM>::solution;
        auto & total_length = EmstSolver<DIM>::total_length;

        while (solution.size() + 1 < num_points) {
            node_approximation.assign(tree.get_maximal_id() + 1, std::numeric_limits<double>::max());
            nearest_set.assign(num_points, { std::numeric_limits<double>::max(), Edge(0,0) });

            check_fully_connected(tree.get_root_id());

            find_component_neighbors(tree.get_root_id(), tree.get_root_id());

            for (size_t i = 0; i < num_points; i++) {
                if (i == dsu.get_set(i)) {
                    Edge e = nearest_set[i].second;
                    if (dsu.unite(e.first, e.second)) {
                        solution.push_back(e);
                        total_length += nearest_set[i].first;
                    }
                }
            }
        }
    }

    void find_component_neighbors(size_t q, size_t r, size_t depth = 0) {
        if (is_fully_connected[q] && is_fully_connected[r] &&
            dsu.is_in_same_set(tree.points_begin(q)->get_id(), tree.points_begin(r)->get_id())) {
            return;
        }
        if (distance(tree.get_bounding_box(q), tree.get_bounding_box(r)) > node_approximation[q]) {
            return;
        }
        if (tree.is_leaf(q) && tree.is_leaf(r)) {
            node_approximation[q] = 0.0;
            for (auto i = tree.points_begin(q); i != tree.points_end(q); i++) {
                for (auto j = tree.points_begin(r); j != tree.points_end(r); j++) {
                    if (!dsu.is_in_same_set(i->get_id(), j->get_id())) {
                        double dist = distance(*i, *j);
                        if (dist < nearest_set[dsu.get_set(i->get_id())].first) {
                            nearest_set[dsu.get_set(i->get_id())] = { dist, { i->get_id(), j->get_id() } };
                        }
                    }
                }
                node_approximation[q] = std::max(node_approximation[q], nearest_set[dsu.get_set(i->get_id())].first);
            }
        } else {
            size_t qleft = tree.get_left_child_id(q);
            size_t qright = tree.get_right_child_id(q);
            size_t rleft = tree.get_left_child_id(r);
            size_t rright = tree.get_right_child_id(r);
            if (tree.is_leaf(q)) {
                find_component_neighbors(q, rleft, depth);
                find_component_neighbors(q, rright, depth);
                return;
            }
            if (tree.is_leaf(r)) {
                find_component_neighbors(qleft, r, depth);
                find_component_neighbors(qright, r, depth);
                node_approximation[q] = std::max(node_approximation[qleft], node_approximation[qright]);
                return;
            }
            find_component_neighbors(qleft, rleft, depth + 1);
            find_component_neighbors(qleft, rright, depth + 1);
            find_component_neighbors(qright, rright, depth + 1);
            find_component_neighbors(qright, rleft, depth + 1);
            node_approximation[q] = std::max(node_approximation[qleft], node_approximation[qright]);
        }
    }

    void check_fully_connected(size_t node_id) {
        if (is_fully_connected[node_id]) {
            return;
        }
        if (tree.is_leaf(node_id)) {
            bool fully_connected = true;
            for (auto iter = tree.points_begin(node_id); iter + 1 != tree.points_end(node_id); ++iter) {
                fully_connected &= dsu.is_in_same_set(iter->get_id(), (iter + 1)->get_id());
            }
            is_fully_connected[node_id] = fully_connected;
            return;
        }
        size_t left = tree.get_left_child_id(node_id);
        size_t right = tree.get_right_child_id(node_id);
        check_fully_connected(left);
        check_fully_connected(right);
        if (is_fully_connected[left] && is_fully_connected[right] &&
            dsu.is_in_same_set(tree.points_begin(left)->get_id(), tree.points_begin(right)->get_id())) {
            is_fully_connected[node_id] = true;
        }
    }

    size_t num_points;
    DSU dsu;
    KdTree<DIM> tree;
    std::vector<bool> is_fully_connected;
    std::vector<double> node_approximation;
    std::vector<std::pair<double, Edge>> nearest_set;
};

/// emst done

/**
 * Prim's algorithm
 * Time complexity: O(N^2)
 */
template<size_t DIM>
class PrimSolver : public EmstSolver<DIM> {
public:
    PrimSolver(const std::vector<Point<DIM>> & points) {
        solve(points);
    }

private:
    void solve(const std::vector<Point<DIM>> & points) {
        auto & solution = EmstSolver<DIM>::solution;
        auto & total_length = EmstSolver<DIM>::total_length;
        size_t num_points = points.size();

        std::vector<std::pair<double, size_t>> distance_to_tree(num_points, { std::numeric_limits<double>::max(), 0 });
        std::vector<bool> used(num_points, false);
        used[0] = true;
        for (size_t i = 1; i < num_points; i++) {
            distance_to_tree[i] = { distance(points[0], points[i]), 0 };
        }

        for (size_t iteration = 1; iteration < num_points; iteration++) {
            size_t nearest_id = 0;
            for (size_t i = 1; i < num_points; i++) {
                if (!used[i] && distance_to_tree[i] < distance_to_tree[nearest_id]) {
                    nearest_id = i;
                }
            }
            solution.push_back({ nearest_id, distance_to_tree[nearest_id].second });
            total_length += distance_to_tree[nearest_id].first;
            used[nearest_id] = true;
            for (size_t i = 1; i < num_points; i++) {
                if (!used[i] && distance(points[i], points[nearest_id]) < distance_to_tree[i].first) {
                    distance_to_tree[i] = { distance(points[i], points[nearest_id]) , nearest_id };
                }
            }
        }
    }

};
/// prim done


    pair<double,vector<pair<point,point>>> get_fast_mst_edges_and_score(vector<point>&a){

        vector<Point<2>>points(a.size());

        for(int i=0;i<a.size();i++){
            points[i][0]=a[i].x;
            points[i][1]=a[i].y;
        }

        KdTreeSolver<2> solver_fast(points);

        vector<pair<size_t, size_t>>edges=solver_fast.get_solution();
        vector<pair<point,point>> ret;
        for(int i=0;i<edges.size();i++){
            ret.pb({ point(points[edges[i].ff][0],points[edges[i].ff][1],0) , point(points[edges[i].ss][0],points[edges[i].ss][1],0) });
            ///printf("%d %d EDGE\n",edges[i].ff,edges[i].ss);
        }
        ///printf("%d RET\n",ret.size());


        return {solver_fast.get_total_length(),ret};

    }

    pair<double,vector<pair<int,int>>> get_fast_mst_edges_by_id_and_score(vector<point>&a){

        vector<Point<2>>points(a.size());

        for(int i=0;i<a.size();i++){
            points[i][0]=a[i].x;
            points[i][1]=a[i].y;
        }

        KdTreeSolver<2> solver_fast(points);

        vector<pair<size_t, size_t>>edges=solver_fast.get_solution();
        vector<pair<int,int>> ret;
        for(int i=0;i<edges.size();i++){
            ret.pb({edges[i].ff,edges[i].ss});
            ///printf("%d %d EDGE\n",edges[i].ff,edges[i].ss);
        }
        ///printf("%d RET\n",ret.size());


        return {solver_fast.get_total_length(),ret};

    }

    pair<double,vector<pair<point,point>>> get_slow_mst_edges_and_score(vector<point>&a){

        vector<Point<2>>points(a.size());

        for(int i=0;i<a.size();i++){
            points[i][0]=a[i].x;
            points[i][1]=a[i].y;
        }

        PrimSolver<2> solver_fast(points);

        vector<pair<size_t, size_t>>edges=solver_fast.get_solution();
        vector<pair<point,point>> ret;
        for(int i=0;i<edges.size();i++){
            ret.pb({ point(points[edges[i].ff][0],points[edges[i].ff][1],0) , point(points[edges[i].ss][0],points[edges[i].ss][1],0) });
            ///printf("%d %d EDGE\n",edges[i].ff,edges[i].ss);
        }
        ///printf("%d RET\n",ret.size());


        return {solver_fast.get_total_length(),ret};

    }

}


const int maxn=5e4+10;
int n,m;
vector<point>soldiers,towers;

namespace my_kdtree{

    int wrong_cnt=0;

    struct my_kdt{

        vector<point>pts;
        vector<pair<pii,int>>tree;

        void build(int x,int l,int r,vector<pair<int,point>>&niz,int dep){

            if(l>r)return;
            if(l==r){
                tree[x].ff.ff=niz[l].ff;
                tree[x].ff.ss=1;
                tree[x].ss=1;
                return;
            }

            int mid=(l+r)/2;

            if(dep==0)sort(niz.begin()+l,niz.begin()+r+1,[](pair<int,point> &a,pair<int,point> &b){
                return a.ss.x<b.ss.x;
            });
            else sort(niz.begin()+l,niz.begin()+r+1,[](pair<int,point> &a,pair<int,point> &b){
                return a.ss.y<b.ss.y;
            });

            tree[x].ff.ff=niz[mid].ff;
            tree[x].ff.ss=1;
            tree[x].ss=1;

            build(x*2,l,mid-1,niz,dep^1);
            build(x*2+1,mid+1,r,niz,dep^1);

            tree[x].ff.ss+=tree[x*2].ff.ss+tree[x*2+1].ff.ss;

        }

        my_kdt(vector<point>&pts){

            this->pts=pts;
            tree.resize(4*pts.size()+1);

            vector<pair<int,point>>niz(pts.size());
            for(int i=0;i<pts.size();i++)niz[i]={i,pts[i]};

            ///cout<<"start build"<<endl;
            build(1,0,pts.size()-1,niz,0);
            ///cout<<"end build"<<endl;

        }

        my_kdt(vector<pii>&pom){

            vector<point>pts(pom.size());
            for(int i=0;i<pom.size();i++)
                pts[i]={pom[i].ff,pom[i].ss,0};


            this->pts=pts;
            tree.resize(4*pts.size()+1);

            vector<pair<int,point>>niz(pts.size());
            for(int i=0;i<pts.size();i++)niz[i]={i,pts[i]};

            ///cout<<"start build"<<endl;
            build(1,0,pts.size()-1,niz,0);
            ///cout<<"end build"<<endl;

        }

        inline ll get_dist(point &p,point &c){
            return (p.x-(ll)c.x)*(p.x-(ll)c.x)+(p.y-(ll)c.y)*(p.y-(ll)c.y);
        }
        void update_best(point target,int &best,int id){

            if(best==-1){
                best=id;
                return;
            }

            if(get_dist(pts[best],target)>get_dist(target,pts[id]))best=id;

        }
        void nearest_neighbour(int x,point &target,int &best_id,int dep){

            if(tree[x].ff.ss==0)return;

            int id=tree[x].ff.ff;

            int nxt_node,other_node;
            nxt_node=x*2;
            other_node=x*2+1;
            if(dep==0){
                if(target.x<=pts[id].x){}
                else swap(nxt_node,other_node);
            }
            else{
                if(target.y<=pts[id].y){}
                else swap(nxt_node,other_node);
            }

            if(tree[x].ss)update_best(target,best_id,id);

            nearest_neighbour(nxt_node,target,best_id,dep^1);

            ll pom=(target.x-(ll)pts[id].x)*(target.x-(ll)pts[id].x);
            if(dep)pom=(target.y-(ll)pts[id].y)*(target.y-(ll)pts[id].y);

            ///cout<<get_dist(pts[best_id],target)<<" "<<pom<<"  DIST"<<endl;

            if(best_id==-1 || get_dist(pts[best_id],target)>pom){
                nearest_neighbour(other_node,target,best_id,dep^1);
                wrong_cnt++;
            }

        }

        void delete_node(int x,point val,int dep){

            int id=tree[x].ff.ff;

            if(pts[id].x==val.x && pts[id].y==val.y){
                tree[x].ff.ss--;
                tree[x].ss--;
                return;
            }

            if(dep==0){
                if(val.x<=pts[id].x)delete_node(x*2,val,dep^1);
                else delete_node(x*2+1,val,dep^1);
            }
            else{
                if(val.y<=pts[id].y)delete_node(x*2,val,dep^1);
                else delete_node(x*2+1,val,dep^1);
            }

            tree[x].ff.ss=tree[x].ss+tree[x*2].ff.ss+tree[x*2+1].ff.ss;

        }

    };

}

namespace TSP{
    vector<int>vect[maxn];
    int pos[maxn];

    struct operation{
        pii p1,p2;
        int w;
    };
    struct gamestate{

        map<pair<int,int>,int>pts;
        vector<operation>ops;
        double score;

        gamestate(vector<point>&a,vector<point>&b){

            score=0;
            ops.clear();

            for(int i=0;i<a.size();i++)
            pts[{a[i].x,a[i].y}]=a[i].w;

            for(int i=0;i<b.size();i++)
            pts[{b[i].x,b[i].y}]=-b[i].w;

        }

        int new_count(int sold,int tow){

            if(tow<0){

                tow=abs(tow);
                if(sold>=tow){
                    return ceil(sqrt((ll)sold*(ll)sold-(ll)tow*(ll)tow));
                }
                else{
                    swap(sold,tow);
                    return -ceil(sqrt((ll)sold*(ll)sold-(ll)tow*(ll)tow));
                }
            }
            else{
                return sold+tow;
            }

        }

        double static calc_dist(pii a,pii b){
            return sqrt( ((ll)a.ff-b.ff)*((ll)a.ff-b.ff)+((ll)a.ss-b.ss)*((ll)a.ss-b.ss) );
        }

        void do_operation(operation op){

            map<pii,int>::iterator sit=pts.find(op.p1);

            if(sit==pts.end()){
                cout<<"losa operacija"<<endl;
                return;
            }
            if(sit->ss<op.w || op.w<=0){
                cout<<"losa operacija 2"<<endl;
                return;
            }

            sit->ss-=op.w;

            score+=op.w*calc_dist(op.p1,op.p2);

            pts[op.p2]=new_count(op.w,pts[op.p2]);

            ops.pb(op);

        }

        void ispis(){
            cout<<ops.size()<<endl;
            for(int i=0;i<ops.size();i++)
                cout<<ops[i].p1.ff<<" "<<ops[i].p1.ss<<" "<<ops[i].p2.ff<<" "<<ops[i].p2.ss<<" "<<ops[i].w<<endl;
        }


        bool point_exists(pii a){
            if(pts.find(a)==pts.end())return 0;
            return 1;
        }

    };
    struct gamestate_light{

        set<pii>pts;
        vector<operation>ops;
        double score;


        gamestate_light(){}

        gamestate_light(vector<point>&a){

            score=0;
            ops.clear();

            for(int i=0;i<a.size();i++)
            pts.insert({a[i].x,a[i].y});

        }

        int static new_count(int sold,int tow){

            if(tow<0){

                tow=abs(tow);
                if(sold>=tow){
                    return ceil(sqrt((ll)sold*(ll)sold-(ll)tow*(ll)tow));
                }
                else{
                    swap(sold,tow);
                    return -ceil(sqrt((ll)sold*(ll)sold-(ll)tow*(ll)tow));
                }
            }
            else{
                return sold+tow;
            }

        }

        double static calc_dist(pii a,pii b){
            return sqrt( ((ll)a.ff-b.ff)*((ll)a.ff-b.ff)+((ll)a.ss-b.ss)*((ll)a.ss-b.ss) );
        }

        void do_operation(operation op){
            score+=op.w*calc_dist(op.p1,op.p2);
            if(op.w<=0){
                cout<<"LOSA OPERACIJAAAAAAAAAAAAAAAAAAAA "<<op.w<<endl;
            }
            ops.pb(op);
        }

        void ispis(){
            cout<<ops.size()<<endl;
            for(int i=0;i<ops.size();i++)
                cout<<ops[i].p1.ff<<" "<<ops[i].p1.ss<<" "<<ops[i].p2.ff<<" "<<ops[i].p2.ss<<" "<<ops[i].w<<endl;
        }


        bool point_exists(pii a){
            if(pts.find(a)==pts.end())return 0;
            return 1;
        }

        pii find_close_free_point(int xs,int ys){
            while(point_exists({xs,ys})){
                xs++;
            }
            return {xs,ys};
        }

    };

    pii gathering_point(vector<point>&a,gamestate_light &g){

        if(a.size()==1){
            return {a[0].x,a[0].y};
        }

        ll xs,ys,cnt;
        xs=ys=cnt=0;

        for(int i=0;i<a.size();i++){
            xs=xs+(ll)a[i].x*(ll)a[i].w;
            ys=ys+(ll)a[i].y*(ll)a[i].w;
            cnt+=(ll)a[i].w;
        }
        xs/=cnt;
        ys/=cnt;

        while(g.point_exists({xs,ys})){
            xs++;
        }

        return {xs,ys};
    }

    void go_euler_tour_tree(int x,int prv,vector<int>&p){
        p.pb(x);
        for(int i=0;i<vect[x].size();i++){
            int id=vect[x][i];
            if(id==prv)continue;
            go_euler_tour_tree(id,x,p);
        }
        p.pb(x);
    }
    vector<int> get_TSP(vector<point>&a){

        vector<pii>edges=emst_namespace::get_fast_mst_edges_by_id_and_score(a).ss;
        for(int i=0;i<a.size();i++){
            vect[i].clear();
            pos[i]=0;
        }

        for(int i=0;i<edges.size();i++){
            int u=edges[i].ff;
            int v=edges[i].ss;
            vect[u].pb(v);
            vect[v].pb(u);
        }

        vector<int>path;
        go_euler_tour_tree(0,-1,path);

        vector<int>ret;
        for(int i=0;i<path.size();i++){
            int id=path[i];
            if(pos[id])continue;

            pos[id]=1;
            ret.pb(id);
        }

        return ret;
    }

    double dd;
    int cdd;
    void apply_TSP(vector<point>&a,vector<point>&b,gamestate_light &g){/// a -> moji vojnici

        if(a.size()==0 || b.size()==0)return;

        pii c=gathering_point(a,g);
        int curr=0;
        for(int i=0;i<a.size();i++){
            operation op;
            op.p1={a[i].x,a[i].y};
            op.p2=c;
            op.w=a[i].w;
            g.do_operation(op);
            curr+=op.w;
        }

        vector<int>path=get_TSP(b);
        for(int i=0;i<path.size();i++){
            int id=path[i];
            pii nw={b[id].x,b[id].y};

            operation op;
            op.p1=c;
            op.p2=nw;
            op.w=curr;

            g.do_operation(op);

            curr=g.new_count(curr,-b[id].w);
            c=nw;
        }

        /*dd=0;
        for(int i=1;i<path.size();i++){
            int id=path[i];
            int id2=path[i-1];
            dd+=g.calc_dist({b[id].x,b[id].y},{b[id2].x,b[id2].y});
        }

        cdd=curr;*/
    }


    vector<int> get_greedy(vector<point>&a,pii start){

        my_kdtree::my_kdt ds(a);

        point s;
        s.x=start.ff;
        s.y=start.ss;

        vector<int>ret;
        for(int i=0;i<a.size();i++){

            ///if(i%1000==0)cout<<i<<" "<<a.size()<<endl;

            int best=-1;
            ds.nearest_neighbour(1,s,best,0);

            ///cout<<i<<" "<<my_kdtree::wrong_cnt<<"  cnt"<<endl;

            my_kdtree::wrong_cnt=0;

            if(best==-1){
                cout<<"NE RADI"<<endl;
                while(1){}
            }

            ds.delete_node(1,a[best],0);

            ret.pb(best);

            s=a[best];
        }

        return ret;
    }
    void apply_greedy(vector<point>&a,vector<point>&b,gamestate_light &g){/// a -> moji vojnici

        if(a.size()==0 || b.size()==0)return;

        pii c=gathering_point(a,g);
        int curr=0;
        for(int i=0;i<a.size();i++){
            operation op;
            op.p1={a[i].x,a[i].y};
            op.p2=c;
            op.w=a[i].w;
            g.do_operation(op);
            curr+=op.w;
        }

        ///cout<<"get gready"<<endl;
        vector<int>path=get_greedy(b,c);
        ///cout<<"done greedy"<<endl;
        for(int i=0;i<path.size();i++){
            int id=path[i];
            pii nw={b[id].x,b[id].y};

            operation op;
            op.p1=c;
            op.p2=nw;
            op.w=curr;

            g.do_operation(op);

            curr=g.new_count(curr,-b[id].w);
            c=nw;
        }

        /*dd=0;
        for(int i=1;i<path.size();i++){
            int id=path[i];
            int id2=path[i-1];
            dd+=g.calc_dist({b[id].x,b[id].y},{b[id2].x,b[id2].y});
        }

        cdd=curr;*/
    }

    vector<point> pick_soldier_candidates_simple(vector<point>&soldiers,vector<point>&towers){

        ll tower_sum=0;
        for(int i=0;i<towers.size();i++)
            tower_sum+=(ll)towers[i].w*(ll)towers[i].w;

        vector<point>ret;
        ll soldier_sum=0;
        for(int i=0;i<soldiers.size();i++){
            soldier_sum+=(ll)soldiers[i].w;
            ret.pb(soldiers[i]);
            if(soldier_sum*soldier_sum>=tower_sum)break;
        }

        return ret;
    }

    gamestate_light simple_example(vector<point> soldiers,vector<point> towers){

        gamestate_light g(towers);
        vector<point> cand=pick_soldier_candidates_simple(soldiers,towers);
        apply_TSP(cand,towers,g);

        return g;
    }

    gamestate_light simple_example_greedy(vector<point> soldiers,vector<point> towers){

        gamestate_light g(towers);
        vector<point> cand=pick_soldier_candidates_simple(soldiers,towers);
        apply_greedy(cand,towers,g);

        return g;
    }
}


namespace K_means{

    mt19937 gen(10);
    const int max_c=1000000000;
    const int max_k=50000;

    ll tower_sqr_cnt[max_k];
    ll sumx[max_k],sumy[max_k],cnt[max_k];
    bool soldier_pos[maxn];

    vector<pii> init_centroids(int k,vector<point>&p){

        vector<pii> ret(k);

        for(int i=0;i<k;i++){
            int pom=gen();
            int pom2=gen();
            if(pom<0)pom=-pom;
            if(pom2<0)pom2=-pom2;
            pom%=max_c+1;
            pom2%=max_c+1;
            ret[i]={ pom,pom2 };
        }

        return ret;
    }

    inline ll get_dist(point &p,pii &c){
        return (p.x-(ll)c.ff)*(p.x-(ll)c.ff)+(p.y-(ll)c.ss)*(p.y-(ll)c.ss);
    }
    void do_iteration(vector<pii>&c,vector<point>&p){

        for(int j=0;j<c.size();j++)
            cnt[j]=sumx[j]=sumy[j]=0;

        my_kdtree::my_kdt ds(c);
        for(int i=0;i<p.size();i++){

            ll pom;
            ll min_dist=3e18;
            int min_ind=-1;
            ds.nearest_neighbour(1,p[i],min_ind,0);
            /*
            for(int j=0;j<c.size();j++){
                pom=get_dist(p[i],c[j]);
                if(pom<min_dist){
                    min_dist=pom;
                    min_ind=j;
                }
            }*/

            cnt[min_ind]++;
            sumx[min_ind]+=(ll)p[i].x;
            sumy[min_ind]+=(ll)p[i].y;

        }

        /// proveri za c da li je cnt==0
        for(int j=0;j<c.size();j++){
            if(cnt[j]==0)
                continue;

            c[j].ff=sumx[j]/cnt[j];
            c[j].ss=sumy[j]/cnt[j];
        }

    }

    vector<pii> get_K_centroids(int k,vector<point>&p,int iter){

        vector<pii>centroids=init_centroids(k,p);

        for(int i=0;i<iter;i++)
            do_iteration(centroids,p);

        return centroids;
    }


    pair<ll,ll> calc_sums(vector<point>&soldiers,vector<point>&towers){

        ll sums=0;
        for(int i=0;i<soldiers.size();i++){
            sums+=soldiers[i].w;
        }

        ll sumt=0;
        for(int i=0;i<towers.size();i++){
            sumt+=(ll)towers[i].w*(ll)towers[i].w;
        }

        return {sums,sumt};
    }
    int get_incorrect_ind(vector<pair<ll,ll>>&calcs){

        for(int i=0;i<calcs.size();i++){
            ///cout<<i<<" "<<calcs[i].ff<<" "<<calcs[i].ss<<" CALC"<<endl;
            if(calcs[i].ff*calcs[i].ff<calcs[i].ss)return i;
        }

        return -1;
    }
    inline ll calc_dist(pii &a,pii &b){
        return ((ll)a.ff-b.ff)*((ll)a.ff-b.ff)+((ll)a.ss-b.ss)*((ll)a.ss-b.ss);
    }
    int find_closest_centroid(vector<pii>&c,int id){

        int ret=-1;
        ll mindist=-1;
        for(int i=0;i<c.size();i++){
            if(id==i)continue;
            if(c[i].ff==-1)continue;

            if(ret==-1){
                ret=i;
                mindist=calc_dist(c[i],c[id]);
            }
            else{

                ll pom=calc_dist(c[i],c[id]);
                if(pom<mindist){
                    pom=mindist;
                    ret=i;
                }

            }

        }

        return ret;
    }
    void merge_groups(vector<vector<point>>&soldiers,vector<vector<point>>&towers,vector<pii>&c,vector<pair<ll,ll>>&calcs,int id,int id2){

        for(int i=0;i<soldiers[id2].size();i++){
            soldiers[id].pb(soldiers[id2][i]);
        }
        soldiers[id2].clear();
        for(int i=0;i<towers[id2].size();i++){
            towers[id].pb(towers[id2][i]);
        }
        towers[id2].clear();

        calcs[id]=calc_sums(soldiers[id],towers[id]);
        calcs[id2]={0,0};

        c[id2]={-1,-1};
        ll sumx=0;
        ll sumy=0;
        ll cnt=0;
        for(int i=0;i<towers[id].size();i++){
            cnt++;
            sumx+=towers[id][i].x;
            sumy+=towers[id][i].y;
        }
        sumx/=cnt;
        sumy/=cnt;
        c[id]={sumx,sumy};

    }
    void make_corrections(vector<vector<point>>&soldiers,vector<vector<point>>&towers,vector<pii>&c){

        vector<pair<ll,ll>>calcs(c.size());

        for(int i=0;i<c.size();i++)calcs[i]=calc_sums(soldiers[i],towers[i]);

        ///cout<<"stigao"<<endl;
        while(1){


            int id=get_incorrect_ind(calcs);
            if(id==-1)break;

            int id2=find_closest_centroid(c,id);

            ///cout<<"opala"<<" "<<id<<" "<<id2<<endl;


            merge_groups(soldiers,towers,c,calcs,id,id2);
        }

    }



    pii curr_centroid;
    vector<point>curr_soldiers;
    bool cmp(int a,int b){
        ///return get_dist(curr_soldiers[a],curr_centroid)<get_dist(curr_soldiers[b],curr_centroid);
        return abs(curr_soldiers[a].x-curr_centroid.ff)+abs(curr_soldiers[a].y-curr_centroid.ss)<abs(curr_soldiers[b].x-curr_centroid.ff)+abs(curr_soldiers[b].y-curr_centroid.ss);
        ///return a<b;
    }
    TSP::gamestate_light do_K_means(int k,vector<point>&s,vector<point>&p,int iter){

        vector<pii>centroids=get_K_centroids(k,p,iter);
        /*for(int i=0;i<k;i++){
            printf("%d %d Centroid\n",centroids[i].ff,centroids[i].ss);
        }*/

        vector<vector<point>>centroid_towers(k),centroid_soldiers(k);

        for(int i=0;i<centroids.size();i++)
            tower_sqr_cnt[i]=0;

        my_kdtree::my_kdt cds(centroids);
        for(int i=0;i<p.size();i++){

            ll pom;
            ll min_dist=3e18;
            int min_ind=-1;
            cds.nearest_neighbour(1,p[i],min_ind,0);
            /*for(int j=0;j<centroids.size();j++){
                pom=get_dist(p[i],centroids[j]);
                if(pom<min_dist){
                    min_dist=pom;
                    min_ind=j;
                }
            }*/

            tower_sqr_cnt[min_ind]+=(ll)p[i].w*(ll)p[i].w;

            centroid_towers[min_ind].pb(p[i]);

        }


        vector<int>niz(s.size());
        for(int i=0;i<s.size();i++){
            niz[i]=i;
            soldier_pos[i]=0;
        }
        curr_soldiers=s;
        my_kdtree::my_kdt ds(s);
        for(int i=0;i<centroids.size();i++){

            if(tower_sqr_cnt[i]==0)continue;

            ///curr_centroid=centroids[i];


            /// SORTIRANJE MNOGO VREMENA ODUZME
            ///if(k<25)sort(niz.begin(),niz.end(),cmp);
            ///sort(niz.begin(),niz.end(),cmp);

            point center;
            center.x=centroids[i].ff;
            center.y=centroids[i].ss;
            center.w=0;

            ll curr_sum=0;
            int cc=0;
            ///for(int j=0;j<s.size();j++){
            while(1){
                int id=-1;
                ds.nearest_neighbour(1,center,id,0);

                if(id==-1)break;

                cc++;

                curr_sum+=s[id].w;
                centroid_soldiers[i].pb(s[id]);
                ds.delete_node(1,s[id],0);
                if(curr_sum*curr_sum>tower_sqr_cnt[i])break;
            }
            ///cout<<i<<" "<<cc<<" CNT"<<endl;


        }

        make_corrections(centroid_soldiers,centroid_towers,centroids);


        TSP::gamestate_light ret(p);
        for(int i=0;i<k;i++){
            ///TSP::apply_TSP(centroid_soldiers[i],centroid_towers[i],ret);
            TSP::apply_greedy(centroid_soldiers[i],centroid_towers[i],ret);
        }

        return ret;
    }


}



namespace greedy_matching{


    /// sortiras towere
    /// izaberes soldiere za tower, pobrisessoldiere usput dok ih uzimas

    /// uzmes kolko oces vojnika, ali poslednjeg uzmes isto celog, pa vratis ostatak nazad
    /// ovako dokle god je suma vojnika manja od sume towera
    /// znaci sve ih prvo ulogoris na neku blizu tacku pa onda gurnes gde treba

    double scale_coef=1;
    bool tower_cmp(point &a,point &b){
        return (a.x<b.x)||((a.x==b.x)&&(a.y<b.y));
    }
    TSP::gamestate_light apply_greedy_matching(vector<point>a,vector<point>b){

        my_kdtree::my_kdt ds(a);
        ///sort(b.begin(),b.end(),tower_cmp);

        TSP::gamestate_light g(b);

        int soldier_sum=0;
        int tower_sum=0;
        for(int i=0;i<a.size();i++){
            soldier_sum+=a[i].w;
        }
        for(int i=0;i<b.size();i++){
            tower_sum+=b[i].w;
        }

        int acnt=a.size();
        for(int i=0;i<b.size();i++){

            int goal=b[i].w;

            ///cout<<"CURR BI: "<<i<<" "<<soldier_sum<<" "<<tower_sum<<endl;

            vector<int>cand;
            int curr_sum=0;

            if(soldier_sum>=tower_sum)scale_coef=1;

            while(goal*scale_coef>(double)curr_sum){
                int pom=-1;
                ds.nearest_neighbour(1,b[i],pom,0);
                ///cout<<pom<<" "<<a[pom].w<<"  SOLD"<<endl;
                if(pom==-1){

                    cout<<"acnt: "<<acnt<<endl;

                    while(1){}
                }
                cand.pb(pom);
                if(a[pom].w<=0){
                    cout<<"LOSE RADI MATCHING"<<endl;
                }
                curr_sum+=a[pom].w;
                if(goal*scale_coef>(double)curr_sum){
                    acnt--;
                    ds.delete_node(1,a[pom],0);
                }
            }


            if(soldier_sum>=tower_sum){
            //if(0==1){

                pii gpoint=g.find_close_free_point(b[i].x,b[i].y);

                int cg=goal;
                for(int j=0;j<cand.size();j++){
                    int id=cand[j];
                    int cost=min(cg,a[id].w);

                    a[id].w-=cost;
                    cg-=cost;
                    TSP::operation op;
                    op.p1={a[id].x,a[id].y};
                    op.p2=gpoint;
                    op.w=cost;

                ///cout<<"start op"<<endl;
                    g.do_operation(op);

                ///cout<<"end op"<<endl;

                }

                TSP::operation op;
                op.p1=gpoint;
                op.p2={b[i].x,b[i].y};
                op.w=goal;
                g.do_operation(op);

                soldier_sum-=goal;
                tower_sum-=goal;

                int lst=cand.back();
                if(a[lst].w==0)ds.delete_node(1,a[lst],0);

            }
            else{

                pii gpoint=g.find_close_free_point(b[i].x,b[i].y);


                for(int j=0;j<cand.size();j++){
                    int id=cand[j];
                    int cost=a[id].w;

                    ///cout<<id<<" "<<cost<<"   COST"<<endl;

                    a[id].w=0;
                    TSP::operation op;
                    op.p1={a[id].x,a[id].y};
                    op.p2=gpoint;
                    op.w=cost;
                    g.do_operation(op);

                }

                TSP::operation op;
                op.p1=gpoint;
                op.p2={b[i].x,b[i].y};
                op.w=curr_sum;
                g.do_operation(op);

                tower_sum-=goal;
                soldier_sum-=curr_sum;

                int lst=cand.back();
                a[lst].w=g.new_count(curr_sum,-goal);
                soldier_sum+=a[lst].w;

                op.p1=op.p2;
                op.w=a[lst].w;
                op.p2={a[lst].x,a[lst].y};
                if(op.w>0)g.do_operation(op);
                else ds.delete_node(1,a[lst],0);

                ///cout<<op.w<<"  LEFT"<<endl;

                /*for(int j=0;j<cand.size();j++){
                    int id=cand[j];
                    int cost=a[id].w;

                    cout<<id<<" "<<cost<<"   COST222"<<endl;
                }*/

            }

        }

        return g;

    }

}


int subtask=-1;
int main(){

    cin.tie(0);
    ios_base::sync_with_stdio(0);

    freopen("war.in","r",stdin);
    freopen("war.out","w",stdout);

    cin>>n>>m;

    soldiers.resize(n);
    towers.resize(m);
    for(int i=0;i<n;i++){
        ///scanf("%d %d %d",&soldiers[i].x,&soldiers[i].y,&soldiers[i].w);
        cin>>soldiers[i].x>>soldiers[i].y>>soldiers[i].w;
    }
    random_shuffle(soldiers.begin(),soldiers.end());
    int maxw=0;
    for(int i=0;i<m;i++){
        ///scanf("%d %d %d",&towers[i].x,&towers[i].y,&towers[i].w);
        cin>>towers[i].x>>towers[i].y>>towers[i].w;
        maxw=max(maxw,towers[i].w);
    }
    random_shuffle(towers.begin(),towers.end());

    if(maxw>4690)subtask=5;
    else if(maxw>1300)subtask=4;
    else if(maxw>360)subtask=3;
    else if(maxw>100)subtask=2;
    else subtask=1;

    ///pair<double,vector<pair<point,point>>>pom=emst_namespace::get_fast_mst_edges_and_score(towers);

    /*pair<double,vector<pair<point,point>>>pom=emst_namespace::get_fast_mst_edges_and_score(soldiers);
    cout<<pom.ff<<endl;
    for(int i=0;i<pom.ss.size();i++){
        ///printf("%d %d | %d %d\n",pom.ss[i].ff.x,pom.ss[i].ff.y,pom.ss[i].ss.x,pom.ss[i].ss.y);
    }

    pom=emst_namespace::get_slow_mst_edges_and_score(soldiers);
    cout<<pom.ff<<endl;
    for(int i=0;i<pom.ss.size();i++){
        ///printf("%d %d | %d %d\n",pom.ss[i].ff.x,pom.ss[i].ff.y,pom.ss[i].ss.x,pom.ss[i].ss.y);
    }*/


    ///TSP::gamestate_light g=TSP::simple_example(soldiers,towers);
    TSP::gamestate_light g;

    if(subtask==5){
        g=TSP::simple_example_greedy(soldiers,towers);
        ///g=K_means::do_K_means(1,soldiers,towers,10);
    }
    else if(subtask==4){
        g=K_means::do_K_means(17,soldiers,towers,10);
    }
    else if(subtask==3){
        g=K_means::do_K_means(220,soldiers,towers,10);
    }
    else if(subtask==2){
        g=K_means::do_K_means(2500,soldiers,towers,10);
        ///g=K_means::do_K_means(150,soldiers,towers,2);
        ///g=greedy_matching::apply_greedy_matching(soldiers,towers);
    }
    else{
        ///g=K_means::do_K_means(150,soldiers,towers,2);
        g=greedy_matching::apply_greedy_matching(soldiers,towers);
    }

    ///cout<<pow(g.score,2.0/3.0)<<"  SCORE"<<endl;

    g.ispis();


return 0;
}