10
5 1 33242121
5 7 535463871
9 1 202863787
5 4 874413088
6 1 623012241
6 8 786659185
10 5 164281028
9 2 851489092
3 9 169897037
10
9 7
7 7
5 9
6 1
3 6
6 5
2 3
7 7
8 9
7 2
 10
3 1 278114804
3 7 453886464
8 7 830020662
8 2 759298564
9 2 147615930
2 4 617310668
10 2 921400635
2 5 185694079
6 2 157439659
10
4 3
7 7
9 4
2 4
4 1
6 3
7 2
1 10
4 5
1 9
 10
3 1 278114804
3 7 453886464
8 7 830020662
8 2 759298564
9 2 147615930
9 4 617310668
10 4 921400635
4 5 185694079
6 4 157439659
10
4 3
7 7
9 4
2 4
4 1
6 3
7 2
1 10
4 5
1 9
 10
3 1 940484348
1 2 683105297
6 1 34326471
6 7 846216720
10 3 913688945
6 5 62114151
4 2 895808279
3 9 73879870
8 10 274103932
10
10 6
5 8
3 5
7 10
6 6
2 4
1 5
6 4
8 6
9 10
 10
3 1 278114804
1 7 453886464
8 1 830020662
1 2 759298564
9 1 147615930
1 4 617310668
10 1 921400635
1 5 185694079
6 1 157439659
10
4 3
7 7
9 4
2 4
4 1
6 3
7 2
1 10
4 5
1 9
 10
7 1 948825254
7 8 163731103
5 7 24781877
1 9 873109737
6 5 922157259
6 4 695796614
3 8 710123832
5 2 229846714
10 2 126680384
10
1 6
3 7
2 1
10 4
5 1
9 9
10 8
4 2
7 3
1 8
 10
3 1 278114804
3 7 453886464
8 7 830020662
8 2 759298564
9 2 147615930
9 4 617310668
10 4 921400635
10 5 185694079
6 5 157439659
10
4 3
7 7
9 4
2 4
4 1
6 3
7 2
1 10
4 5
1 9
 10
3 1 278114804
3 7 453886464
8 1 830020662
8 2 759298564
9 1 147615930
9 4 617310668
10 1 921400635
10 5 185694079
6 1 157439659
10
4 3
7 7
9 4
2 4
4 1
6 3
7 2
1 10
4 5
1 9

754602117
941306036
345159140
889751864
221567087
452330243
610417136
941306036
595859331
524414191
 154209178
787444642
453508248
220845981
811407029
585833802
738688277
482446523
570228330
938497929
 153593825
962975972
258291347
478762666
561612109
329362801
914219607
371538245
906952313
964451612
 799905193
189641085
247256971
16810814
597350254
995209118
212122928
806020836
286406008
266027678
 249228255
490830292
244045360
106498909
338602533
608288211
212101232
448454413
43032819
251819024
 307488562
936965007
669306706
472217029
103977612
445047045
340459197
439153232
484754007
867070884
 859089925
583743823
284988364
199943666
267108202
191221580
534987458
420592815
717499524
997368329
 203173178
722185173
839677047
956076405
781508643
309964349
11590066
259439789
320401300
152672030

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Egor Kulikov (egor@egork.net)
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        final long mod = (long) (1e9 + 7);
        int n;
        int[] from;
        int[] to;
        int[] w;
        BidirectionalGraph gr;
        LCA lca;
        long[] cnt;
        long[] sumL;
        long[] sumL2;
        long[] cntUp;
        long[] sumLUp;
        long[] sumL2Up;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            n = in.readInt();
            from = new int[n - 1];
            to = new int[n - 1];
            w = new int[n - 1];
            IOUtils.readIntArrays(in, from, to, w);
            MiscUtils.decreaseByOne(from, to);
            gr = BidirectionalGraph.createWeightedGraph(n, from, to, ArrayUtils.asLong(w));
            lca = new LCA(gr);

            cnt = new long[n];
            sumL = new long[n];
            sumL2 = new long[n];
            dfs(0, -1);

            cntUp = new long[n];
            sumLUp = new long[n];
            sumL2Up = new long[n];
            dfsUp(0, -1);

            long[] dist = ShortestDistance.dijkstraAlgorithm(gr, 0).first;
            int Q = in.readInt();
            for (int iter = 0; iter < Q; iter++) {
                int u = in.readInt() - 1;
                int v = in.readInt() - 1;
                int lcaUV = lca.getLCA(u, v);
                long d = dist[v] + dist[u] - 2 * dist[lcaUV];

                long s0, s1;
                if (lcaUV == v) {
                    s1 = f(sumLUp[v], sumL2Up[v], d, cntUp[v]);
                    s0 = sumL2[u] + sumL2Up[u] - s1;
                    s0 %= mod;
//                out.printLine("1): " + IntegerUtils.trueMod(s0 - s1, mod));
//            } else if (lcaUV == u) {
//                out.printLine("hui");
                } else {
                    s0 = sumL2[v] + 2 * d * sumL[v] % mod + d * d % mod * cnt[v] % mod;
                    s0 %= mod;
                    s1 = sumL2[u] + sumL2Up[u] - s0;
//                out.printLine("2): " + IntegerUtils.trueMod(s0 - s1, mod));
                }
                out.printLine(IntegerUtils.trueMod(s0 - s1, mod));
            }
        }

        long f(long sumL, long sumL2, long d, long cnt) {
            return (sumL2 + 2 * d % mod * sumL + d * d % mod * cnt % mod) % mod;
        }

        private void dfsUp(int v, int p) {
            for (int id = gr.firstOutbound(v); id != -1; id = gr.nextOutbound(id)) {
                int to = gr.destination(id);
                if (to == p) continue;

                cntUp[to] = cntUp[v] + cnt[v] - cnt[to];
                sumLUp[to] = sumL[v] - (cnt[to] * gr.weight(id) % mod + sumL[to]) +
                        sumLUp[v] +
                        cntUp[to] * gr.weight(id) % mod;
                sumL2Up[to] = f(sumLUp[v], sumL2Up[v], gr.weight(id), cntUp[v]) +
                        f((sumL[v] - cnt[to] * gr.weight(id) % mod - sumL[to]) % mod,
                                sumL2[v] - f(sumL[to], sumL2[to], gr.weight(id), cnt[to]),
                                gr.weight(id),
                                cnt[v] - cnt[to]);

                cntUp[to] %= mod;
                sumLUp[to] %= mod;
                sumL2Up[to] %= mod;

                dfsUp(to, v);
            }

        }

        private void dfs(int v, int p) {
            cnt[v] = 1;
            for (int id = gr.firstOutbound(v); id != -1; id = gr.nextOutbound(id)) {
                int to = gr.destination(id);
                if (to == p) continue;
                dfs(to, v);
                cnt[v] += cnt[to];
                sumL[v] += cnt[to] * gr.weight(id) % mod + sumL[to];
                sumL2[v] += f(sumL[to], sumL2[to], gr.weight(id), cnt[to]);
            }
            cnt[v] %= mod;
            sumL[v] %= mod;
            sumL2[v] %= mod;
        }

    }

    static class IntegerUtils {
        public static int longCompare(long a, long b) {
            if (a < b)
                return -1;
            if (a > b)
                return 1;
            return 0;
        }

        public static long trueMod(long a, long b) {
            a %= b;
            a += b;
            a %= b;
            return a;
        }

    }

    static class Pair<U, V> implements Comparable<Pair<U, V>> {
        public final U first;
        public final V second;

        public static <U, V> Pair<U, V> makePair(U first, V second) {
            return new Pair<U, V>(first, second);
        }

        private Pair(U first, V second) {
            this.first = first;
            this.second = second;
        }


        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pair pair = (Pair) o;

            return !(first != null ? !first.equals(pair.first) : pair.first != null) && !(second != null ? !second.equals(pair.second) : pair.second != null);

        }


        public int hashCode() {
            int result = first != null ? first.hashCode() : 0;
            result = 31 * result + (second != null ? second.hashCode() : 0);
            return result;
        }


        public String toString() {
            return "(" + first + "," + second + ")";
        }

        @SuppressWarnings({"unchecked"})
        public int compareTo(Pair<U, V> o) {
            int value = ((Comparable<U>) first).compareTo(o.first);
            if (value != 0)
                return value;
            return ((Comparable<V>) second).compareTo(o.second);
        }

    }

    static class IOUtils {
        public static void readIntArrays(InputReader in, int[]... arrays) {
            for (int i = 0; i < arrays[0].length; i++) {
                for (int j = 0; j < arrays.length; j++)
                    arrays[j][i] = in.readInt();
            }
        }

    }

    static class LCA {
        private final long[] order;
        private final int[] position;
        private final Graph graph;
        private final IntervalTree lcaTree;
        private final int[] level;

        public LCA(Graph graph) {
            this(graph, 0);
        }

        public LCA(Graph graph, int root) {
            this.graph = graph;
            order = new long[2 * graph.vertexCount() - 1];
            position = new int[graph.vertexCount()];
            level = new int[graph.vertexCount()];
            int[] index = new int[graph.vertexCount()];
            for (int i = 0; i < index.length; i++)
                index[i] = graph.firstOutbound(i);
            int[] last = new int[graph.vertexCount()];
            int[] stack = new int[graph.vertexCount()];
            stack[0] = root;
            int size = 1;
            int j = 0;
            last[root] = -1;
            Arrays.fill(position, -1);
            while (size > 0) {
                int vertex = stack[--size];
                if (position[vertex] == -1)
                    position[vertex] = j;
                order[j++] = vertex;
                if (last[vertex] != -1)
                    level[vertex] = level[last[vertex]] + 1;
                while (index[vertex] != -1 && last[vertex] == graph.destination(index[vertex]))
                    index[vertex] = graph.nextOutbound(index[vertex]);
                if (index[vertex] != -1) {
                    stack[size++] = vertex;
                    stack[size++] = graph.destination(index[vertex]);
                    last[graph.destination(index[vertex])] = vertex;
                    index[vertex] = graph.nextOutbound(index[vertex]);
                }
            }
            lcaTree = new ReadOnlyIntervalTree(order) {

                protected long joinValue(long left, long right) {
                    if (left == -1)
                        return right;
                    if (right == -1)
                        return left;
                    if (level[((int) left)] < level[((int) right)])
                        return left;
                    return right;
                }


                protected long neutralValue() {
                    return -1;
                }
            };
            lcaTree.init();
        }

        public int getLCA(int first, int second) {
            return (int) lcaTree.query(Math.min(position[first], position[second]), Math.max(position[first], position[second]));
        }

    }

    static class ShortestDistance {
        public static Pair<long[], int[]> dijkstraAlgorithm(Graph graph, int source) {
            int vertexCount = graph.vertexCount();
            final long[] distance = new long[vertexCount];
            int[] last = new int[vertexCount];
            Arrays.fill(distance, Long.MAX_VALUE);
            Arrays.fill(last, -1);
            distance[source] = 0;
            if (graph.isSparse()) {
                Heap heap = new Heap(vertexCount, new IntComparator() {
                    public int compare(int first, int second) {
                        return IntegerUtils.longCompare(distance[first], distance[second]);
                    }
                }, vertexCount);
                heap.add(source);
                while (!heap.isEmpty()) {
                    int current = heap.poll();
                    int id = graph.firstOutbound(current);
                    while (id != -1) {
                        int next = graph.destination(id);
                        long total = graph.weight(id) + distance[current];
                        if (distance[next] > total) {
                            distance[next] = total;
                            if (heap.getIndex(next) == -1)
                                heap.add(next);
                            else
                                heap.shiftUp(heap.getIndex(next));
                            last[next] = id;
                        }
                        id = graph.nextOutbound(id);
                    }
                }
            } else {
                boolean[] visited = new boolean[vertexCount];
                for (int i = 0; i < vertexCount; i++) {
                    int index = -1;
                    long length = Long.MAX_VALUE;
                    for (int j = 0; j < vertexCount; j++) {
                        if (!visited[j] && distance[j] < length) {
                            length = distance[j];
                            index = j;
                        }
                    }
                    if (index == -1)
                        break;
                    visited[index] = true;
                    int id = graph.firstOutbound(index);
                    while (id != -1) {
                        int next = graph.destination(id);
                        if (!visited[next]) {
                            long total = graph.weight(id) + length;
                            if (distance[next] > total) {
                                distance[next] = total;
                                last[next] = id;
                            }
                        }
                        id = graph.nextOutbound(id);
                    }
                }
            }
            return Pair.makePair(distance, last);
        }

    }

    static abstract class ReadOnlyIntervalTree extends IntervalTree {
        protected long[] value;
        protected long[] array;

        protected ReadOnlyIntervalTree(long[] array) {
            super(array.length, false);
            this.array = array;
            init();
        }


        protected void initData(int size, int nodeCount) {
            value = new long[nodeCount];
        }


        protected void initAfter(int root, int left, int right, int middle) {
            value[root] = joinValue(value[2 * root + 1], value[2 * root + 2]);
        }


        protected void initBefore(int root, int left, int right, int middle) {
        }


        protected void initLeaf(int root, int index) {
            value[root] = array[index];
        }


        protected long queryPostProcess(int root, int left, int right, int from, int to, int middle, long leftResult, long rightResult) {
            return joinValue(leftResult, rightResult);
        }


        protected void queryPreProcess(int root, int left, int right, int from, int to, int middle) {
        }


        protected long queryFull(int root, int left, int right, int from, int to) {
            return value[root];
        }


        protected long emptySegmentResult() {
            return neutralValue();
        }

        protected abstract long neutralValue();

        protected abstract long joinValue(long left, long right);

    }

    static class BidirectionalGraph extends Graph {
        public int[] transposedEdge;

        public BidirectionalGraph(int vertexCount) {
            this(vertexCount, vertexCount);
        }

        public BidirectionalGraph(int vertexCount, int edgeCapacity) {
            super(vertexCount, 2 * edgeCapacity);
            transposedEdge = new int[2 * edgeCapacity];
        }

        public static BidirectionalGraph createWeightedGraph(int vertexCount, int[] from, int[] to, long[] weight) {
            BidirectionalGraph graph = new BidirectionalGraph(vertexCount, from.length);
            for (int i = 0; i < from.length; i++)
                graph.addWeightedEdge(from[i], to[i], weight[i]);
            return graph;
        }


        public int addEdge(int fromID, int toID, long weight, long capacity, int reverseEdge) {
            int lastEdgeCount = edgeCount;
            super.addEdge(fromID, toID, weight, capacity, reverseEdge);
            super.addEdge(toID, fromID, weight, capacity, reverseEdge == -1 ? -1 : reverseEdge + 1);
            this.transposedEdge[lastEdgeCount] = lastEdgeCount + 1;
            this.transposedEdge[lastEdgeCount + 1] = lastEdgeCount;
            return lastEdgeCount;
        }


        protected int entriesPerEdge() {
            return 2;
        }


        protected void ensureEdgeCapacity(int size) {
            if (size > edgeCapacity()) {
                super.ensureEdgeCapacity(size);
                transposedEdge = resize(transposedEdge, edgeCapacity());
            }
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static interface IntComparator {
        public static final IntComparator DEFAULT = new IntComparator() {
            public int compare(int first, int second) {
                if (first < second)
                    return -1;
                if (first > second)
                    return 1;
                return 0;
            }
        };

        public int compare(int first, int second);

    }

    static class MiscUtils {
        public static void decreaseByOne(int[]... arrays) {
            for (int[] array : arrays) {
                for (int i = 0; i < array.length; i++)
                    array[i]--;
            }
        }

    }

    static abstract class IntervalTree {
        protected int size;

        protected IntervalTree(int size) {
            this(size, true);
        }

        public IntervalTree(int size, boolean shouldInit) {
            this.size = size;
            int nodeCount = Math.max(1, Integer.highestOneBit(size) << 2);
            initData(size, nodeCount);
            if (shouldInit)
                init();
        }

        protected abstract void initData(int size, int nodeCount);

        protected abstract void initAfter(int root, int left, int right, int middle);

        protected abstract void initBefore(int root, int left, int right, int middle);

        protected abstract void initLeaf(int root, int index);

        protected abstract long queryPostProcess(int root, int left, int right, int from, int to, int middle, long leftResult, long rightResult);

        protected abstract void queryPreProcess(int root, int left, int right, int from, int to, int middle);

        protected abstract long queryFull(int root, int left, int right, int from, int to);

        protected abstract long emptySegmentResult();

        public void init() {
            if (size == 0)
                return;
            init(0, 0, size - 1);
        }

        private void init(int root, int left, int right) {
            if (left == right) {
                initLeaf(root, left);
            } else {
                int middle = (left + right) >> 1;
                initBefore(root, left, right, middle);
                init(2 * root + 1, left, middle);
                init(2 * root + 2, middle + 1, right);
                initAfter(root, left, right, middle);
            }
        }

        public long query(int from, int to) {
            return query(0, 0, size - 1, from, to);
        }

        protected long query(int root, int left, int right, int from, int to) {
            if (left > to || right < from)
                return emptySegmentResult();
            if (left >= from && right <= to)
                return queryFull(root, left, right, from, to);
            int middle = (left + right) >> 1;
            queryPreProcess(root, left, right, from, to, middle);
            long leftResult = query(2 * root + 1, left, middle, from, to);
            long rightResult = query(2 * root + 2, middle + 1, right, from, to);
            return queryPostProcess(root, left, right, from, to, middle, leftResult, rightResult);
        }

    }

    static interface Edge {
    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void printLine(long i) {
            writer.println(i);
        }

    }

    static class Heap {
        private IntComparator comparator;
        private int size = 0;
        private int[] elements;
        private int[] at;

        public Heap(int maxElement) {
            this(10, maxElement);
        }

        public Heap(IntComparator comparator, int maxElement) {
            this(10, comparator, maxElement);
        }

        public Heap(int capacity, int maxElement) {
            this(capacity, IntComparator.DEFAULT, maxElement);
        }

        public Heap(int capacity, IntComparator comparator, int maxElement) {
            this.comparator = comparator;
            elements = new int[capacity];
            at = new int[maxElement];
            Arrays.fill(at, -1);
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public int add(int element) {
            ensureCapacity(size + 1);
            elements[size] = element;
            at[element] = size;
            shiftUp(size++);
            return at[element];
        }

        public void shiftUp(int index) {
//		if (index < 0 || index >= size)
//			throw new IllegalArgumentException();
            int value = elements[index];
            while (index != 0) {
                int parent = (index - 1) >>> 1;
                int parentValue = elements[parent];
                if (comparator.compare(parentValue, value) <= 0) {
                    elements[index] = value;
                    at[value] = index;
                    return;
                }
                elements[index] = parentValue;
                at[parentValue] = index;
                index = parent;
            }
            elements[0] = value;
            at[value] = 0;
        }

        public void shiftDown(int index) {
            if (index < 0 || index >= size)
                throw new IllegalArgumentException();
            while (true) {
                int child = (index << 1) + 1;
                if (child >= size)
                    return;
                if (child + 1 < size && comparator.compare(elements[child], elements[child + 1]) > 0)
                    child++;
                if (comparator.compare(elements[index], elements[child]) <= 0)
                    return;
                swap(index, child);
                index = child;
            }
        }

        public int getIndex(int element) {
            return at[element];
        }

        private void swap(int first, int second) {
            int temp = elements[first];
            elements[first] = elements[second];
            elements[second] = temp;
            at[elements[first]] = first;
            at[elements[second]] = second;
        }

        private void ensureCapacity(int size) {
            if (elements.length < size) {
                int[] oldElements = elements;
                elements = new int[Math.max(2 * elements.length, size)];
                System.arraycopy(oldElements, 0, elements, 0, this.size);
            }
        }

        public int poll() {
            if (isEmpty())
                throw new IndexOutOfBoundsException();
            int result = elements[0];
            at[result] = -1;
            if (size == 1) {
                size = 0;
                return result;
            }
            elements[0] = elements[--size];
            at[elements[0]] = 0;
            shiftDown(0);
            return result;
        }

    }

    static class Graph {
        public static final int REMOVED_BIT = 0;
        protected int vertexCount;
        protected int edgeCount;
        private int[] firstOutbound;
        private int[] firstInbound;
        private Edge[] edges;
        private int[] nextInbound;
        private int[] nextOutbound;
        private int[] from;
        private int[] to;
        private long[] weight;
        public long[] capacity;
        private int[] reverseEdge;
        private int[] flags;

        public Graph(int vertexCount) {
            this(vertexCount, vertexCount);
        }

        public Graph(int vertexCount, int edgeCapacity) {
            this.vertexCount = vertexCount;
            firstOutbound = new int[vertexCount];
            Arrays.fill(firstOutbound, -1);

            from = new int[edgeCapacity];
            to = new int[edgeCapacity];
            nextOutbound = new int[edgeCapacity];
            flags = new int[edgeCapacity];
        }

        public int addEdge(int fromID, int toID, long weight, long capacity, int reverseEdge) {
            ensureEdgeCapacity(edgeCount + 1);
            if (firstOutbound[fromID] != -1)
                nextOutbound[edgeCount] = firstOutbound[fromID];
            else
                nextOutbound[edgeCount] = -1;
            firstOutbound[fromID] = edgeCount;
            if (firstInbound != null) {
                if (firstInbound[toID] != -1)
                    nextInbound[edgeCount] = firstInbound[toID];
                else
                    nextInbound[edgeCount] = -1;
                firstInbound[toID] = edgeCount;
            }
            this.from[edgeCount] = fromID;
            this.to[edgeCount] = toID;
            if (capacity != 0) {
                if (this.capacity == null)
                    this.capacity = new long[from.length];
                this.capacity[edgeCount] = capacity;
            }
            if (weight != 0) {
                if (this.weight == null)
                    this.weight = new long[from.length];
                this.weight[edgeCount] = weight;
            }
            if (reverseEdge != -1) {
                if (this.reverseEdge == null) {
                    this.reverseEdge = new int[from.length];
                    Arrays.fill(this.reverseEdge, 0, edgeCount, -1);
                }
                this.reverseEdge[edgeCount] = reverseEdge;
            }
            if (edges != null)
                edges[edgeCount] = createEdge(edgeCount);
            return edgeCount++;
        }

        protected final Graph.GraphEdge createEdge(int id) {
            return new Graph.GraphEdge(id);
        }

        public final int addFlowWeightedEdge(int from, int to, long weight, long capacity) {
            if (capacity == 0) {
                return addEdge(from, to, weight, 0, -1);
            } else {
                int lastEdgeCount = edgeCount;
                addEdge(to, from, -weight, 0, lastEdgeCount + entriesPerEdge());
                return addEdge(from, to, weight, capacity, lastEdgeCount);
            }
        }

        protected int entriesPerEdge() {
            return 1;
        }

        public final int addWeightedEdge(int from, int to, long weight) {
            return addFlowWeightedEdge(from, to, weight, 0);
        }

        public final int vertexCount() {
            return vertexCount;
        }

        protected final int edgeCapacity() {
            return from.length;
        }

        public final int firstOutbound(int vertex) {
            int id = firstOutbound[vertex];
            while (id != -1 && isRemoved(id))
                id = nextOutbound[id];
            return id;
        }

        public final int nextOutbound(int id) {
            id = nextOutbound[id];
            while (id != -1 && isRemoved(id))
                id = nextOutbound[id];
            return id;
        }

        public final int destination(int id) {
            return to[id];
        }

        public final long weight(int id) {
            if (weight == null)
                return 0;
            return weight[id];
        }

        public final boolean flag(int id, int bit) {
            return (flags[id] >> bit & 1) != 0;
        }

        public final boolean isRemoved(int id) {
            return flag(id, REMOVED_BIT);
        }

        protected void ensureEdgeCapacity(int size) {
            if (from.length < size) {
                int newSize = Math.max(size, 2 * from.length);
                if (edges != null)
                    edges = resize(edges, newSize);
                from = resize(from, newSize);
                to = resize(to, newSize);
                nextOutbound = resize(nextOutbound, newSize);
                if (nextInbound != null)
                    nextInbound = resize(nextInbound, newSize);
                if (weight != null)
                    weight = resize(weight, newSize);
                if (capacity != null)
                    capacity = resize(capacity, newSize);
                if (reverseEdge != null)
                    reverseEdge = resize(reverseEdge, newSize);
                flags = resize(flags, newSize);
            }
        }

        protected final int[] resize(int[] array, int size) {
            int[] newArray = new int[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        private long[] resize(long[] array, int size) {
            long[] newArray = new long[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        private Edge[] resize(Edge[] array, int size) {
            Edge[] newArray = new Edge[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        public final boolean isSparse() {
            return vertexCount == 0 || edgeCount * 20 / vertexCount <= vertexCount;
        }

        protected class GraphEdge implements Edge {
            protected int id;

            protected GraphEdge(int id) {
                this.id = id;
            }

        }

    }

    static class ArrayUtils {
        public static long[] asLong(int[] array) {
            long[] result = new long[array.length];
            for (int i = 0; i < array.length; i++)
                result[i] = array[i];
            return result;
        }

    }
}

