#!/usr/bin/env python3
"""Static nonnegative integer-weight trees, two independent query reductions.
Standard library; stdout only; explicit checks also run under python -O.
No edge updates or unmark operation. Diagnostics are separate from query costs.
"""
import sys
sys.dont_write_bytecode = True
from itertools import product, combinations
from collections import deque
import json
import random


def require(ok, why):
    if not ok:
        raise ValueError(why)


class Tree:
    def __init__(self, n, edges):
        require(type(n) is int and n >= 1, 'positive exact-integer vertex count')
        require(type(edges) in (list, tuple) and len(edges) == n - 1, 'n-1 edges required')
        self.n = n
        adj = [[] for _ in range(n)]
        for edge in edges:
            require(type(edge) in (list, tuple) and len(edge) == 3, 'edge triple')
            u, v, w = edge
            self.vertex(u); self.vertex(v)
            require(u != v and type(w) is int and w >= 0, 'nonloop nonnegative integer edge')
            adj[u].append((v, w)); adj[v].append((u, w))
        seen = {0}; todo = [0]
        while todo:
            u = todo.pop()
            for v, _ in adj[u]:
                if v not in seen:
                    seen.add(v); todo.append(v)
        require(len(seen) == n, 'connected tree required')
        # A connected undirected graph with n-1 nonloop edges cannot have a
        # parallel edge or a cycle. Freeze an independent copy of all inputs.
        self.adj = tuple(tuple(row) for row in adj)

    def vertex(self, v):
        require(type(v) is int and 0 <= v < self.n, 'vertex identity')


class CentroidNearest:
    def __init__(self, tree):
        self.tree = tree; n = tree.n
        self.parent = [None] * n
        self.labels = [[] for _ in range(n)]
        self.certificates = []
        self.adjacency_probes = 0
        blocked = [False] * n
        jobs = [(0, None)]
        while jobs:
            start, cp = jobs.pop()
            order = []; par = {start: None}; todo = [start]
            while todo:
                u = todo.pop(); order.append(u)
                for v, _ in tree.adj[u]:
                    self.adjacency_probes += 1
                    if not blocked[v] and v != par[u]:
                        par[v] = u; todo.append(v)
            size = {u: 1 for u in order}
            for u in reversed(order):
                if par[u] is not None:
                    size[par[u]] += size[u]
            m = len(order); candidates = []
            for u in order:
                largest = m - size[u]
                for v, _ in tree.adj[u]:
                    self.adjacency_probes += 1
                    if par.get(v) == u:
                        largest = max(largest, size[v])
                if 2 * largest <= m:
                    candidates.append(u)
            require(candidates, 'centroid exists')
            c = min(candidates)
            self.parent[c] = cp
            todo = [(c, None, 0)]
            while todo:
                u, p, distance = todo.pop()
                self.labels[u].append((c, distance))
                for v, w in tree.adj[u]:
                    self.adjacency_probes += 1
                    if not blocked[v] and v != p:
                        todo.append((v, u, distance + w))
            parts = []
            for v, _ in tree.adj[c]:
                self.adjacency_probes += 1
                if not blocked[v]:
                    parts.append(size[v] if par.get(v) == c else m - size[c])
                    jobs.append((v, c))
            self.certificates.append({'centroid': c, 'size': m, 'parts': parts, 'parent': cp})
            blocked[c] = True
        self.reset()

    def reset(self):
        self.best = [None] * self.tree.n
        self.marked = [False] * self.tree.n

    def mark(self, v):
        self.tree.vertex(v)
        if self.marked[v]:
            return False
        self.marked[v] = True
        for c, distance in self.labels[v]:
            pair = (distance, v)
            if self.best[c] is None or pair < self.best[c]:
                self.best[c] = pair
        return True

    def candidates(self, v):
        self.tree.vertex(v)
        return [{'centroid': c, 'distance_to_centroid': d,
                 'nearest_mark_at_centroid': None if self.best[c] is None else list(self.best[c]),
                 'candidate': None if self.best[c] is None else d + self.best[c][0]}
                for c, d in self.labels[v]]

    def nearest(self, v):
        self.tree.vertex(v)
        answer = None
        for c, d in self.labels[v]:
            if self.best[c] is not None:
                value, mark = self.best[c]
                candidate = (d + value, mark, c)
                if answer is None or candidate < answer:
                    answer = candidate
        return None if answer is None else dict(zip(('distance', 'mark', 'via'), answer))


class RootedIndex:
    def __init__(self, tree, root=0):
        tree.vertex(root)
        self.tree = tree; self.root = root; n = tree.n
        self.tin = [0] * n; self.tout = [0] * n
        self.depth = [0] * n; self.distance = [0] * n
        parent = [root] * n; self.order = []
        todo = [(root, root, False)]
        while todo:
            u, p, exit_step = todo.pop()
            if exit_step:
                self.tout[u] = len(self.order)
                continue
            self.tin[u] = len(self.order); self.order.append(u); parent[u] = p
            todo.append((u, p, True))
            for v, w in reversed(tree.adj[u]):
                if v != p:
                    self.depth[v] = self.depth[u] + 1
                    self.distance[v] = self.distance[u] + w
                    todo.append((v, u, False))
        self.up = [parent]
        for _ in range(1, n.bit_length()):
            row = self.up[-1]
            self.up.append([row[row[v]] for v in range(n)])

    def ancestor(self, u, v):
        return self.tin[u] <= self.tin[v] < self.tout[u]

    def lca(self, u, v):
        self.tree.vertex(u); self.tree.vertex(v)
        if self.ancestor(u, v): return u
        if self.ancestor(v, u): return v
        for row in reversed(self.up):
            if not self.ancestor(row[u], v): u = row[u]
        return self.up[0][u]

    def virtual(self, terminals):
        require(type(terminals) in (list, tuple), 'finite terminal list')
        for v in terminals: self.tree.vertex(v)
        selected = set(terminals)
        ordered = sorted(selected, key=self.tin.__getitem__)
        if not ordered:
            return {'root': None, 'terminals': [], 'nodes': [], 'edges': [],
                    'edge_contributions': [], 'subtree_weight': 0, 'pair_distance_sum': 0}
        closure = set(ordered)
        for u, v in zip(ordered, ordered[1:]):
            closure.add(self.lca(u, v))
        nodes = sorted(closure, key=self.tin.__getitem__)
        stack = []; edges = []; parent = {}
        for v in nodes:
            while stack and not self.ancestor(stack[-1], v): stack.pop()
            if stack:
                p = stack[-1]; parent[v] = p
                edges.append((p, v, self.distance[v] - self.distance[p]))
            stack.append(v)
        count = {v: int(v in selected) for v in nodes}
        contributions = []; k = len(selected)
        for v in reversed(nodes[1:]):
            p = parent[v]; s = count[v]; length = self.distance[v] - self.distance[p]
            contributions.append({'edge': [p, v], 'length': length, 'terminals_below': s,
                                  'unordered_pairs_crossing': s * (k - s),
                                  'contribution': length * s * (k - s)})
            count[p] += s
        require(count[nodes[0]] == k and len(nodes) <= 2 * k - 1, 'virtual tree size/coverage')
        return {'root': nodes[0], 'terminals': ordered, 'nodes': nodes, 'edges': edges,
                'edge_contributions': list(reversed(contributions)),
                'subtree_weight': sum(w for _, _, w in edges),
                'pair_distance_sum': sum(x['contribution'] for x in contributions)}


def all_distances(tree):
    # Direct unique-path traversals, not centroid labels or an LCA formula.
    out = []
    for source in range(tree.n):
        ds = [None] * tree.n; ds[source] = 0; todo = [source]
        while todo:
            u = todo.pop()
            for v, w in tree.adj[u]:
                if ds[v] is None:
                    ds[v] = ds[u] + w; todo.append(v)
        out.append(ds)
    return out


def brute_subtree_weight(tree, selected):
    # A tree edge is in the terminal hull exactly when both deletion sides
    # contain terminals. Explicit graph traversal is intentionally slow.
    if len(selected) <= 1: return 0
    total = 0
    for u in range(tree.n):
        for v, w in tree.adj[u]:
            if u >= v: continue
            seen = {u}; todo = [u]
            while todo:
                x = todo.pop()
                for y, _ in tree.adj[x]:
                    if (x == u and y == v) or (x == v and y == u): continue
                    if y not in seen: seen.add(y); todo.append(y)
            if selected & seen and selected - seen: total += w
    return total


def check_tree(tree, subsets):
    distance = all_distances(tree)
    cd = CentroidNearest(tree); idx = RootedIndex(tree)
    for cert in cd.certificates:
        require(sum(cert['parts']) == cert['size'] - 1, 'component partition')
        require(all(2 * s <= cert['size'] for s in cert['parts']), 'half-size separator')
    require(all(len(x) <= tree.n.bit_length() for x in cd.labels), 'logarithmic labels')
    for v, labels in enumerate(cd.labels):
        require(all(distance[v][c] == d for c, d in labels), 'stored original distance')
    count = 0
    for selected in subsets:
        selected = set(selected); cd.reset()
        for v in selected: cd.mark(v)
        for u in range(tree.n):
            result = cd.nearest(u)
            expected = min(((distance[u][v], v) for v in selected), default=None)
            require((None if result is None else (result['distance'], result['mark'])) == expected, 'nearest marked')
        virtual = idx.virtual(list(selected))
        closure = selected | {idx.lca(u, v) for u in selected for v in selected}
        require(set(virtual['nodes']) == closure, 'all-pairs LCA closure')
        require(virtual['subtree_weight'] == brute_subtree_weight(tree, selected), 'terminal hull')
        require(virtual['pair_distance_sum'] == sum(distance[u][v] for u,v in combinations(selected, 2)), 'unordered pair sum')
        count += 1
    return count


def prufer_tree(n, word):
    if n == 1: return []
    degree = [1] * n
    for v in word: degree[v] += 1
    edges = []
    for v in word:
        u = next(i for i in range(n) if degree[i] == 1)
        edges.append((u, v, 1 + (u + v) % 3)); degree[u] -= 1; degree[v] -= 1
    u, v = [i for i in range(n) if degree[i] == 1]
    edges.append((u, v, 1 + (u + v) % 3))
    return edges


def self_check():
    trees = subsets = 0
    for n in range(1, 6):
        words = [()] if n <= 2 else product(range(n), repeat=n-2)
        for word in words:
            t = Tree(n, prufer_tree(n, word))
            subsets += check_tree(t, ([i for i in range(n) if mask >> i & 1] for mask in range(1 << n)))
            trees += 1
    rng = random.Random(19192026); random_subsets = 0
    for trial in range(180):
        n = rng.randrange(1, 38)
        t = Tree(n, [(v, rng.randrange(v), rng.randrange(8)) for v in range(1,n)])
        random_subsets += check_tree(t, ([v for v in range(n) if rng.randrange(4) == 0] for _ in range(12)))
    # All traversals are iterative, including original trees with huge depth.
    path = Tree(5000, [(i-1, i, 1) for i in range(1,5000)])
    cd = CentroidNearest(path); cd.mark(4999)
    require(cd.nearest(0)['distance'] == 4999, 'deep centroid path')
    idx = RootedIndex(path)
    require(idx.virtual([0,4999])['pair_distance_sum'] == 4999, 'deep virtual path')
    bad = 0
    for call in [lambda: Tree(True, []), lambda: Tree(2,[(0,1,-1)]),
                 lambda: Tree(3,[(0,1,1),(0,1,1)]), lambda: Tree(2,[(0,0,1)]),
                 lambda: cd.mark(True), lambda: idx.virtual([5000]),
                 lambda: RootedIndex(path,True), lambda: Tree(2,[(0,1,True)])]:
        try: call()
        except ValueError: bad += 1
        else: raise RuntimeError('invalid input accepted')
    return {'exhaustive_labeled_trees': trees, 'exhaustive_terminal_subsets': subsets,
            'random_trees':180, 'random_terminal_subsets':random_subsets,
            'deep_path_vertices':5000, 'rejected_inputs':bad}


def fixture():
    return Tree(11, [(0,1,2),(0,2,3),(1,3,1),(1,4,4),(3,5,2),
                     (3,6,1),(2,7,2),(7,8,3),(7,9,1),(9,10,2)])


def main():
    t = fixture(); cd = CentroidNearest(t); idx = RootedIndex(t)
    trace = [{'action':'query6_empty','result':cd.nearest(6)}]
    for mark, query in [(4,6),(8,10),(6,5)]:
        cd.mark(mark)
        trace.append({'mark':mark,'query':query,'candidates':cd.candidates(query),'result':cd.nearest(query)})
    require([x['result']['distance'] for x in trace[1:]] == [6,6,3], 'fixture nearest values')
    require(cd.mark(6) is False and cd.nearest(0)['distance'] == 4, 'idempotent mark and root query')
    first = idx.virtual([4,5,8,10]); transfer = idx.virtual([5,6,10])
    require((first['subtree_weight'],first['pair_distance_sum']) == (20,67), 'first terminal query')
    require((transfer['subtree_weight'],transfer['pair_distance_sum']) == (14,28), 'changed terminal query')
    rerooted = RootedIndex(t,7).virtual([4,5,8,10])
    require((rerooted['subtree_weight'],rerooted['pair_distance_sum']) == (20,67), 'root-independent hull quantities')
    require(idx.virtual([4,4,4])['nodes'] == [4], 'single terminal not original root')
    internal = idx.virtual([1,5])
    require(internal['pair_distance_sum'] == 3, 'internal terminal contributes one')
    numbering = RootedIndex(Tree(5,[(0,1,1),(1,2,1),(0,3,1),(1,4,1)]))
    numbering_result = numbering.virtual([2,3,4])
    wrong_closure = {2,3,4} | {numbering.lca(2,3),numbering.lca(3,4)}
    require(wrong_closure == {0,2,3,4} and numbering_result['subtree_weight'] == 4
            and numbering_result['pair_distance_sum'] == 8, 'numeric-order counterexample')
    input_edges = [[0,1,2]]; copied = Tree(2,input_edges); input_edges[0][2] = 99
    require(copied.adj[0] == ((1,2),), 'tree owns frozen input copy')
    before = (list(cd.best),list(cd.marked))
    try: cd.mark(True)
    except ValueError: pass
    else: raise RuntimeError('Boolean vertex accepted')
    require(before == (cd.best,cd.marked), 'invalid mark leaves state unchanged')
    changed = fixture()
    changed_edges = [(u,v,10 if (u,v)==(1,4) else w)
                     for u in range(changed.n) for v,w in changed.adj[u] if u<v]
    rebuilt = CentroidNearest(Tree(11,changed_edges)); rebuilt.mark(4)
    require(rebuilt.nearest(6)['distance'] == 12, 'changed weight requires rebuild')
    print(json.dumps({'tree':{'n':t.n,'edges':[(u,v,w) for u in range(t.n) for v,w in t.adj[u] if u<v]},
          'centroid_parent':cd.parent,'centroid_certificates':cd.certificates,
          'labels':cd.labels,'marked_query_trace':trace,'preorder':idx.order,
          'virtual_first':first,'virtual_transfer':transfer,'virtual_rerooted':rerooted,
          'empty':idx.virtual([]),'singleton':idx.virtual([4,4,4]),
          'internal_terminal':internal,'numeric_order_counterexample':{
              'correct':numbering_result,'wrong_retained_nodes':sorted(wrong_closure),
              'wrong_subtree_weight':5,'wrong_pair_sum':10},
          'boundary_checks':{'frozen_input_copy':True,'invalid_mark_atomic':True,
                             'changed_weight_rebuilt_distance':rebuilt.nearest(6)['distance']},
          'checks':self_check()},ensure_ascii=False,indent=2))


if __name__ == '__main__':
    main()