Problem: You are given a tree that has n vertices, which are numbered from 1 to n, where the vertex number one is the root. Each edge has weight wi and strength pi.

Botanist Innokentiy, who is the only member of the jury of the Olympiad in Informatics, doesn't like broken trees. 

The tree is broken if there is such an edge the strength of which is less than the sum of weight of subtree's edges to which it leads.

It is allowed to reduce weight of any edge by arbitrary integer value, but then the strength of its edge is reduced by the same value. It means if the weight of the edge is 10, and the strength is 12, then by the reducing the weight by 7 its weight will equal 3, and the strength will equal 5. 

It is not allowed to increase the weight of the edge.

Your task is to get the tree, which is not broken, by reducing the weight of edges of the given tree, and also all edged should have the positive weight, moreover, the total weight of all edges should be as large as possible.

It is obvious that the strength of edges can not be negative, however it can equal zero if the weight of the subtree equals zero. 

Input

The first line contains the integer n (1 ≤ n ≤ 2·105) — the number of vertices in the tree. The next n - 1 lines contains the description of edges. Each line contains four integers x, y, w, p (1 ≤ x, y ≤ n, 1 ≤ w ≤ 109, 0 ≤ p ≤ 109), where x and y — vertices which connect the edge (the vertex number x is the parent of the vertex number y), w and p are the weight and the strength of the edge, accordingly. It is guaranteed that the edges describe the tree with the root in the vertex 1.

Output

If it is impossible to get unbroken tree from the given tree, print -1 in the only line.

Otherwise, the output data should contain n lines:

In the first line print the number n — the number of vertices on the tree. 

In the next n - 1 lines print the description of edges of the resulting tree. Each line should contain four integers x, y, w, p (1 ≤ x, y ≤ n, 1 ≤ w ≤ 109, 0 ≤ p ≤ 109), where x and y — vertices, which the edge connects (the vertex number x is the parent of the vertex number y), w and p are the new weight and the strength of the edge, accordingly. 

Print edges in the same order as they are given in input data: the first two integers of each line should not be changed. 

Examples

Input

3
1 3 5 7
3 2 4 3


Output

3
1 3 5 7
3 2 4 3


Input

4
1 3 2 3
3 4 5 1
3 2 3 3


Output

-1

Input

5
1 2 2 4
2 4 1 9
4 5 5 6
4 3 4 8


Output

5
1 2 2 4
2 4 1 9
4 5 1 2
4 3 2 6


Input

7
1 2 5 2
2 3 4 3
1 4 3 7
4 5 4 1
4 6 3 2
6 7 1 6


Output

7
1 2 5 2
2 3 2 1
1 4 3 7
4 5 3 0
4 6 3 2
6 7 1 6

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.BiFunction;
import java.util.function.Supplier;

public class E {

    private static class Edge {
        private final int from;
        private final int to;
        private long weight;
        private long strength;

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

        public int getFrom() {
            return from;
        }

        public int getTo() {
            return to;
        }

        public long getWeight() {
            return weight;
        }

        public long getStrength() {
            return strength;
        }

        public void cut(long value) {
            if (value < 0) {
                throw new IllegalStateException("Can't increase weights");
            }
            if (value >= weight) {
                throw new IllegalStateException("Cutting " + value + " from edge with weight " + weight);
            }
            if (value > strength) {
                throw new IllegalStateException("Cutting " + value + " from edge with strength " + strength);
            }
            weight -= value;
            strength -= value;
        }

        @Override
        public String toString() {
            return String.format("%d->%d %d/%d", from, to, weight, strength);
        }
    }

    private static class Vertex {
        private final long weight;
        private final long minWeight;
        private final long willCut;

        private Vertex(long weight, long minWeight, long willCut) {
            this.weight = weight;
            this.minWeight = minWeight;
            this.willCut = willCut;
        }

        public long getWeight() {
            return weight;
        }

        public long getMinWeight() {
            return minWeight;
        }

        public long getWillCut() {
            return willCut;
        }
    }

    private static class Gardener {

        private final int n;
        private final List<List<Edge>> tree;
        private List<Vertex> vertices;
        private boolean isBroken;

        public Gardener(int n, List<Edge> edges) {
            this.n = n;
            tree = new ArrayList<>(n - 1);
            for (int i = 0; i < n; i++) {
                tree.add(new ArrayList<>());
            }
            for (Edge e : edges) {
                tree.get(e.getFrom()).add(e);
            }
            vertices = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                vertices.add(new Vertex(0, 0, 0));
            }
            calculateVertices(0);
        }

        private Vertex calculateVertices(int vertex) {
            List<Edge> edges = tree.get(vertex);
            Vertex result;
            long totalCut = 0;
            if (edges.size() == 0) {
                result = new Vertex(0, 0, 0);
                vertices.set(vertex, result);
                return result;
            }
            long weight = 0;
            long minWeight = 0;
            for (Edge edge : edges) {
                Vertex child = calculateVertices(edge.getTo());
                if (child == null) {
                    // fast path return
                    return null;
                }

                // weight and minweight calculations
                weight += edge.getWeight() + child.getWeight();
                minWeight += edge.getWeight() + child.getMinWeight();
                long canCut = Math.max(edge.getStrength() - child.getMinWeight(), 0);
                canCut = Math.min(canCut, edge.getWeight() - 1);
                minWeight -= canCut;

                // calculate willCut
                long childCut = child.getWillCut();
                totalCut += childCut;
                long overweight = Math.max(child.getWeight() - edge.getStrength(), 0);
                overweight = Math.max(overweight - childCut, 0);
                totalCut += overweight;

                if (edge.getStrength() < child.getMinWeight()) {
                    isBroken = true;
                    // fast path return
                    return null;
                }
            }
            result = new Vertex(weight, minWeight, totalCut);
            vertices.set(vertex, result);
            return result;
        }

        public boolean isBroken() {
            return isBroken;
        }

        public void cut() {
            if (!isBroken()) {
                long actuallyCut = cut(0, 0);
                long expectedCut = vertices.get(0).getWillCut();
                if (actuallyCut > expectedCut) {
                    throw new IllegalStateException(String.format("Too aggressive expected to cut %d actually got %d", expectedCut, actuallyCut));
                }
            }
        }

        private long cut(int vertex, long overweight) {
            List<Edge> edges = tree.get(vertex);
            long vertexCut = 0;
            for (Edge edge : edges) {
                Vertex child = vertices.get(edge.getTo());
                // edge overweight which will be redirected to child
                final long edgeToChildOverweight = Math.max(child.getWeight() - child.getWillCut() - edge.getStrength(), 0);
                overweight += edgeToChildOverweight;
                final long childCut = cut(edge.getTo(), overweight);
                if (childCut < child.getWillCut()) {
                    throw new IllegalStateException("Child cut less than expected");
                }

                vertexCut += childCut;
                final long additionalChildCut = childCut - child.getWillCut();
                overweight = Math.max(overweight - additionalChildCut, 0);
                final long childWeightAfterCut = child.getWeight() - childCut;

                long edgeCanCut = Math.max(edge.getStrength() - childWeightAfterCut, 0);
                edgeCanCut = Math.min(edgeCanCut, edge.getWeight() - 1);
                final long edgeCut = Math.min(overweight, edgeCanCut);

                edge.cut(edgeCut);
                vertexCut += edgeCut;
                overweight = Math.max(overweight - edgeCut, 0);
                if (edge.getStrength() < childWeightAfterCut) {
                    throw new IllegalStateException("Violated constraint");
                }
            }
            return vertexCut;
        }
    }

    private static List<Edge> generateInput(int maxLevel,
                                            Supplier<Integer> fanoutSupplier,
                                            BiFunction<Integer, Integer, Integer> weightSupplier,
                                            BiFunction<Integer, Integer, Integer> strengthSupplier
    ) {
        List<Edge> result = new ArrayList<>();
        final AtomicInteger counter = new AtomicInteger();
        generateTree(maxLevel, 0, counter::getAndIncrement, fanoutSupplier, weightSupplier, strengthSupplier, result);
        return result;
    }

    private static Integer generateTree(int maxLevel, int level,
                                        Supplier<Integer> vertexSupplier,
                                        Supplier<Integer> fanoutSupplier,
                                        BiFunction<Integer, Integer, Integer> weightSupplier,
                                        BiFunction<Integer, Integer, Integer> strengthSupplier,
                                        List<Edge> collector) {
        Integer vertex = vertexSupplier.get();
        if (level == maxLevel) {
            return vertex;
        }
        Integer fanout = fanoutSupplier.get();
        for (int i = 0; i < fanout; i++) {
            Integer weight = weightSupplier.apply(level, maxLevel);
            Integer strength = strengthSupplier.apply(level, maxLevel);
            Integer childVertex = generateTree(maxLevel, level + 1, vertexSupplier, fanoutSupplier, weightSupplier, strengthSupplier, collector);
            collector.add(new Edge(vertex, childVertex, weight, strength));
        }
        return vertex;
    }

    private static List<Edge> singleTest() {
        ThreadLocalRandom r = ThreadLocalRandom.current();
        List<Edge> input = generateInput(18, () -> 2, (l, ml) -> r.nextInt(1, 2), (l, ml) -> r.nextInt(1000000, 2000000));
        List<Edge> inputCopy = new ArrayList<>();
        for (Edge e : input) {
            inputCopy.add(new Edge(e.getFrom(), e.getTo(), e.getWeight(), e.getStrength()));
        }
        int n = input.size() + 1;
        try {
            System.out.println("waiting");
            System.in.read();
            System.out.println("Solving problem for n=" + n);
            long l = System.currentTimeMillis();
            Gardener gardener = new Gardener(n, input);
            gardener.cut();
            System.out.println("Elapsed " + (System.currentTimeMillis() - l) + " ms");
            System.out.println("complete");
            System.in.read();
        } catch (Exception e) {
            return inputCopy;
        }
        return null;
    }

    private static void test() throws IOException {
        int n = 1;
        int smallestInput = Integer.MAX_VALUE;
        List<Edge> result = null;
        for (int i = 0; i < n; i++) {
            List<Edge> edges = singleTest();
            if (edges != null && edges.size() < smallestInput) {
                smallestInput = edges.size();
                result = edges;
            }
        }
        if (result == null) {
            System.out.println("Success!");
            return;
        }
        System.out.println("Got breaking input");
        for (Edge edge : result) {
            System.out.println(String.format("%d %d %d %d", edge.getFrom() + 1, edge.getTo() + 1, edge.getWeight(), edge.getStrength()));
        }
        System.exit(-1);
    }

    private static void solve() {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        List<Edge> edges = new ArrayList<>(n - 1);

        for (int i = 0; i < n - 1; i++) {
            int x = s.nextInt() - 1;
            int y = s.nextInt() - 1;
            long w = s.nextInt();
            long st = s.nextInt();
            edges.add(new Edge(x, y, w, st));
        }

        Gardener gardener = new Gardener(n, edges);
        gardener.cut();
        if (gardener.isBroken()) {
            System.out.println(-1);
            return;
        }
        StringBuilder builder = new StringBuilder();
        builder.append(n).append("\n");
        for (Edge edge : edges) {
            builder
                    .append(edge.getFrom() + 1).append(" ")
                    .append(edge.getTo() + 1).append(" ")
                    .append(edge.getWeight()).append(" ")
                    .append(edge.getStrength())
                    .append("\n");
        }
        System.out.println(builder.toString());
    }

    public static void main(String[] args) throws IOException {
        solve();
    }
}