import java.util.*;
import java.util.stream.Stream;

public class ExtremeSpanningTrees {
    static class Edge {
        public int from,to;
        public int weight;
        public int label;

        public Edge(int from, int to, int weight, int label) {
            this.from = from;
            this.to = to;
            this.weight = weight;
            this.label = label;
        }
    }

    public List<Edge>[] graph;
    public boolean[][] tree;
    public boolean[][] conn;
    public long ans;
    public int[] a, b, w;
    public int n,m;
    public long minTime(int[] a, int[] b, int[] w, int[] m1, int[] m2) {
        this.a = a; this.b = b; this.w = w;
        n = m1.length+1; m = a.length;
        graph = Stream.generate(ArrayList::new).limit(n).toArray(List[]::new);
        for (int i = 0; i < m; i++) {
            graph[a[i]].add(new Edge(a[i], b[i], w[i], i));
            graph[b[i]].add(new Edge(b[i], a[i], w[i], i));
        }
        tree = new boolean[2][];
        tree[0] = new boolean[m];
        tree[1] = new boolean[m];
        for (int i = 0; i < n-1; i++) {
            tree[0][m1[i]] = true;
            tree[1][m2[i]] = true;
        }

        prev = new int[n];
        cid = new int[n];
        conn = new boolean[m][m];
        for (int i = 0; i < m; i++) {
            if (!tree[0][i]) {
                prev[a[i]] = -1;
                mark(a[i], b[i], a[i], i, 0);
            }
            if (!tree[1][i]) {
                prev[a[i]] = -1;
                mark(a[i], b[i], a[i], i, 1);
            }
        }

        List<Integer> active = new ArrayList<>();
        for (int i = 0; i < m; i++) active.add(i);
        ans = 0;
        int lo = w[0], hi = w[0];
        for (int i = 1; i < m; i++) {
            lo = Math.min(lo, w[i]);
            hi = Math.max(hi, w[i]);
        }
        solve(lo, hi, active);
        return ans;
    }

    public int[] prev;
    public int[] cid;
    public void mark(int from, int to, int cur, int idx, int dir) {
        if (cur == to) {
            while (cur != from) {
                if (dir == 0) {
                    conn[idx][cid[cur]] = true;
                } else {
                    conn[cid[cur]][idx] = true;
                }
                cur = prev[cur];
            }
            return;
        }

        for (Edge next : graph[cur]) {
            if (!tree[dir][next.label]) continue;
            if (next.to == prev[cur]) continue;
            prev[next.to] = cur;
            cid[next.to] = next.label;
            mark(from, to, next.to, idx, dir);
        }
    }

    public void solve(int lo, int hi, List<Integer> active) {
        if (active.size() == 0) return;
        if (active.size() == 1) {
            int x = active.get(0);
            if (w[x] < lo) ans += lo - w[x];
            if (w[x] > hi) ans += w[x] - hi;
            return;
        }
        if (lo == hi) {
            for (int x : active) {
                ans += Math.abs(lo - w[x]);
            }
            return;
        }

        int mid = (lo + hi) / 2;

        int n = active.size();
        int nnodes = n + 2;
        List<MaxFlowDinic.Edge>[] gg = Stream.generate(ArrayList::new).limit(nnodes).toArray(List[]::new);
        for (int i = 0; i < n; i++) {
            int dd = active.get(i);
            if (w[dd] <= mid) {
                MaxFlowDinic.addEdge(gg, nnodes-1, i, 1);
            } else {
                MaxFlowDinic.addEdge(gg, i, nnodes-2, 1);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (conn[active.get(i)][active.get(j)])
                    MaxFlowDinic.addEdge(gg, i, j, 1 << 30);
            }
        }
        Set<Integer> s = MaxFlowDinic.minCut(gg, nnodes-1, nnodes-2);
        List<Integer> r1 = new ArrayList<>(), r2 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (s.contains(i)) r1.add(active.get(i));
            else r2.add(active.get(i));
        }
        solve(lo, mid, r1);
        solve(mid+1, hi, r2);
    }

    static class MaxFlowDinic {
        public static void addEdge(List<Edge>[] graph, int s, int t, int cap) {
            graph[s].add(new Edge(t, graph[t].size(), cap));
            graph[t].add(new Edge(s, graph[s].size() - 1, 0));
        }

        static boolean dinicBfs(List<Edge>[] graph, int src, int dest, int[] dist) {
            Arrays.fill(dist, -1);
            dist[src] = 0;
            int[] Q = new int[graph.length];
            int sizeQ = 0;
            Q[sizeQ++] = src;
            for (int i = 0; i < sizeQ; i++) {
                int u = Q[i];
                for (Edge e : graph[u]) {
                    if (dist[e.t] < 0 && e.f < e.cap) {
                        dist[e.t] = dist[u] + 1;
                        Q[sizeQ++] = e.t;
                    }
                }
            }
            return dist[dest] >= 0;
        }

        static int dinicDfs(List<Edge>[] graph, int[] ptr, int[] dist, int dest, int u, int f) {
            if (u == dest)
                return f;
            for (; ptr[u] < graph[u].size(); ++ptr[u]) {
                Edge e = graph[u].get(ptr[u]);
                if (dist[e.t] == dist[u] + 1 && e.f < e.cap) {
                    int df = dinicDfs(graph, ptr, dist, dest, e.t, Math.min(f, e.cap - e.f));
                    if (df > 0) {
                        e.f += df;
                        graph[e.t].get(e.rev).f -= df;
                        return df;
                    }
                }
            }
            return 0;
        }

        public static int maxFlow(List<Edge>[] graph, int src, int dest) {
            int flow = 0;
            int[] dist = new int[graph.length];
            while (dinicBfs(graph, src, dest, dist)) {
                int[] ptr = new int[graph.length];
                while (true) {
                    int df = dinicDfs(graph, ptr, dist, dest, src, Integer.MAX_VALUE);
                    if (df == 0)
                        break;
                    flow += df;
                }
            }
            return flow;
        }

        public static Set<Integer> minCut(List<Edge>[] graph, int src, int dest) {
            maxFlow(graph, src, dest);
            Set<Integer> ret = new HashSet<>();
            int n = graph.length;
            int[] queue = new int[n];
            int front = 0, back = 0;
            queue[back++] = src;
            ret.add(src);
            while(front < back) {
                int node = queue[front++];
                for (Edge e : graph[node]) {
                    if (!ret.contains(e.t) && e.f < e.cap) {
                        ret.add(e.t);
                        queue[back++] = e.t;
                    }
                }
            }
            return ret;
        }

        public static class Edge {
            public int t, rev, cap, f;

            public Edge(int t, int rev, int cap) {
                this.t = t;
                this.rev = rev;
                this.cap = cap;
            }
        }
    }
}