{"raw_statement":[{"iden":"statement","content":"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 _w__i_ and strength _p__i_.\n\nBotanist Innokentiy, who is the only member of the jury of the Olympiad in Informatics, doesn't like broken trees.\n\nThe 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.\n\nIt 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.\n\nIt is not allowed to increase the weight of the edge.\n\nYour 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.\n\nIt is obvious that the strength of edges can not be negative, however it can equal zero if the weight of the subtree equals zero."},{"iden":"input","content":"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."},{"iden":"output","content":"If it is impossible to get unbroken tree from the given tree, print _\\-1_ in the only line.\n\nOtherwise, the output data should contain _n_ lines:\n\nIn the first line print the number _n_ — the number of vertices on the tree.\n\nIn 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.\n\nPrint edges in the same order as they are given in input data: the first two integers of each line should not be changed."},{"iden":"examples","content":"Input\n\n3\n1 3 5 7\n3 2 4 3\n\nOutput\n\n3\n1 3 5 7\n3 2 4 3\n\nInput\n\n4\n1 3 2 3\n3 4 5 1\n3 2 3 3\n\nOutput\n\n\\-1\n\nInput\n\n5\n1 2 2 4\n2 4 1 9\n4 5 5 6\n4 3 4 8\n\nOutput\n\n5\n1 2 2 4\n2 4 1 9\n4 5 1 2\n4 3 2 6\n\nInput\n\n7\n1 2 5 2\n2 3 4 3\n1 4 3 7\n4 5 4 1\n4 6 3 2\n6 7 1 6\n\nOutput\n\n7\n1 2 5 2\n2 3 2 1\n1 4 3 7\n4 5 3 0\n4 6 3 2\n6 7 1 6"}],"translated_statement":[{"iden":"statement","content":"你被给定一棵有 #cf_span[n] 个顶点的树，顶点编号从 #cf_span[1] 到 #cf_span[n]，其中顶点 #cf_span[1] 为根。每条边有权重 #cf_span[wi] 和强度 #cf_span[pi]。\n\n植物学家 Innokentiy 是信息学奥林匹克竞赛的唯一评审委员，他不喜欢有缺陷的树。\n\n如果存在一条边，其强度小于它所指向的子树中所有边的权重之和，则该树被视为有缺陷。\n\n允许将任意边的权重减少任意整数值，此时该边的强度也会减少相同的值。例如，若一条边的权重为 #cf_span[10]，强度为 #cf_span[12]，则将其权重减少 #cf_span[7] 后，权重变为 #cf_span[3]，强度变为 #cf_span[5]。\n\n不允许增加边的权重。\n\n你的任务是通过减少给定树中边的权重，得到一棵无缺陷的树，同时满足：所有边的权重必须为正数，且所有边的总权重尽可能大。\n\n显然，边的强度不能为负数，但如果子树的权重和为零，则强度可以为零。\n\n第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105]) —— 树中顶点的数量。接下来的 #cf_span[n - 1] 行描述了边。每行包含四个整数 #cf_span[x], #cf_span[y], #cf_span[w], #cf_span[p] (#cf_span[1 ≤ x, y ≤ n, 1 ≤ w ≤ 109, 0 ≤ p ≤ 109])，其中 #cf_span[x] 和 #cf_span[y] 是边连接的两个顶点（顶点 #cf_span[x] 是顶点 #cf_span[y] 的父节点），#cf_span[w] 和 #cf_span[p] 分别是该边的权重和强度。保证这些边构成以顶点 #cf_span[1] 为根的树。\n\n如果无法从给定的树中得到一棵无缺陷的树，请在唯一一行输出 _-1_。\n\n否则，输出应包含 #cf_span[n] 行：\n\n第一行输出数字 #cf_span[n] —— 树中顶点的数量。\n\n接下来的 #cf_span[n - 1] 行输出结果树中每条边的描述。每行应包含四个整数 #cf_span[x], #cf_span[y], #cf_span[w], #cf_span[p] (#cf_span[1 ≤ x, y ≤ n, 1 ≤ w ≤ 109, 0 ≤ p ≤ 109])，其中 #cf_span[x] 和 #cf_span[y] 是边连接的两个顶点（顶点 #cf_span[x] 是顶点 #cf_span[y] 的父节点），#cf_span[w] 和 #cf_span[p] 是该边新的权重和强度。\n\n请按照输入数据的顺序输出边：每行的前两个整数不应改变。"},{"iden":"input","content":"第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105]) —— 树中顶点的数量。接下来的 #cf_span[n - 1] 行描述了边。每行包含四个整数 #cf_span[x], #cf_span[y], #cf_span[w], #cf_span[p] (#cf_span[1 ≤ x, y ≤ n, 1 ≤ w ≤ 109, 0 ≤ p ≤ 109])，其中 #cf_span[x] 和 #cf_span[y] 是边连接的两个顶点（顶点 #cf_span[x] 是顶点 #cf_span[y] 的父节点），#cf_span[w] 和 #cf_span[p] 分别是该边的权重和强度。保证这些边构成以顶点 #cf_span[1] 为根的树。"},{"iden":"output","content":"如果无法从给定的树中得到一棵无缺陷的树，请在唯一一行输出 _-1_。否则，输出应包含 #cf_span[n] 行：第一行输出数字 #cf_span[n] —— 树中顶点的数量。接下来的 #cf_span[n - 1] 行输出结果树中每条边的描述。每行应包含四个整数 #cf_span[x], #cf_span[y], #cf_span[w], #cf_span[p] (#cf_span[1 ≤ x, y ≤ n, 1 ≤ w ≤ 109, 0 ≤ p ≤ 109])，其中 #cf_span[x] 和 #cf_span[y] 是边连接的两个顶点（顶点 #cf_span[x] 是顶点 #cf_span[y] 的父节点），#cf_span[w] 和 #cf_span[p] 是该边新的权重和强度。请按照输入数据的顺序输出边：每行的前两个整数不应改变。"},{"iden":"examples","content":"输入31 3 5 73 2 4 3输出31 3 5 73 2 4 3输入41 3 2 33 4 5 13 2 3 3输出-1输入51 2 2 42 4 1 94 5 5 64 3 4 8输出51 2 2 42 4 1 94 5 1 24 3 2 6输入71 2 5 22 3 4 31 4 3 74 5 4 14 6 3 26 7 1 6输出71 2 5 22 3 2 11 4 3 74 5 3 04 6 3 26 7 1 6"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be a rooted tree with $ n $ vertices, where $ V = \\{1, 2, \\dots, n\\} $ and vertex $ 1 $ is the root.  \nFor each edge $ e = (x, y) \\in E $ (with $ x $ parent of $ y $), define:  \n- $ w_e \\in \\mathbb{Z}^+ $: original weight of edge $ e $,  \n- $ p_e \\in \\mathbb{Z}_{\\geq 0} $: original strength of edge $ e $.  \n\nLet $ S_e $ denote the total weight of all edges in the subtree rooted at $ y $ (i.e., the sum of weights of all edges descending from $ e $).  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^5 $  \n2. For each edge $ e = (x, y) $:  \n   - $ 1 \\leq w_e \\leq 10^9 $,  \n   - $ 0 \\leq p_e \\leq 10^9 $.  \n3. The tree is given with parent-child relationships: for each edge $ (x, y) $, $ x $ is the parent of $ y $.  \n4. **Unbroken Tree Condition**: For every edge $ e = (x, y) $, we require:  \n   $$\n   p_e' \\geq S_e'\n   $$  \n   where $ w_e' $ is the new weight of edge $ e $, $ p_e' = p_e - (w_e - w_e') $ is the new strength, and $ S_e' $ is the total weight of the subtree rooted at $ y $ under the new weights.  \n5. **Feasibility Constraints**:  \n   - $ 1 \\leq w_e' \\leq w_e $ for all $ e \\in E $,  \n   - $ p_e' \\geq 0 $ for all $ e \\in E $,  \n   - $ S_e' \\geq 0 $ for all $ e \\in E $.  \n\n**Objective**  \nMaximize the total weight of the tree:  \n$$\n\\sum_{e \\in E} w_e'\n$$  \nsubject to the above constraints.  \n\nIf no such assignment $ \\{w_e'\\} $ exists, output $-1$.  \nOtherwise, output the tree with updated edge weights $ w_e' $ and strengths $ p_e' = p_e - (w_e - w_e') $, preserving input edge order.","simple_statement":null,"has_page_source":false}