{"raw_statement":[{"iden":"problem statement","content":"You are given $Q$ triples of integers $(a_1, b_1, d_1), (a_2, b_2, d_2), \\ldots, (a_Q, b_Q, d_Q)$.\nA subset $S$ of the set $\\lbrace 1, 2, \\ldots, Q\\rbrace$ is defined to be a **good set** if there exists an integer sequence $(X_1, X_2, \\ldots, X_N)$ of length $N$ that satisfies:\n\n> $X_{a_i} - X_{b_i} = d_i$ for all $i \\in S$.\n\nStarting with $S$ as an empty set, perform the following operation for $i = 1, 2, \\ldots, Q$ in this order:\n\n> If $S \\cup \\lbrace i \\rbrace$ is a good set, then replace $S$ with $S \\cup \\lbrace i \\rbrace$.\n\nPrint all elements of the final set $S$ in **ascending order**."},{"iden":"constraints","content":"*   All input values are integers.\n*   $1 \\leq N, Q \\leq 2 \\times 10^5$\n*   $1 \\leq a_i, b_i \\leq N$\n*   $-10^9 \\leq d_i \\leq 10^9$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $Q$\n$a_1$ $b_1$ $d_1$\n$a_2$ $b_2$ $d_2$\n$\\vdots$\n$a_Q$ $b_Q$ $d_Q$"},{"iden":"sample input 1","content":"3 5\n1 2 2\n3 2 -3\n2 1 -1\n3 3 0\n1 3 5"},{"iden":"sample output 1","content":"1 2 4 5\n\nStarting with $S$ as an empty set, perform the operation described in the problem statement for $i = 1, 2, 3, 4, 5$ in this order, as follows.\n\n*   For $i = 1$, the set $S \\cup \\lbrace i \\rbrace = \\lbrace 1 \\rbrace$ is a good set, because $(X_1, X_2, X_3) = (3, 1, 4)$ satisfies the condition in the problem statement, for example, so replace $S$ with $\\lbrace 1\\rbrace$.\n*   For $i = 2$, the set $S \\cup \\lbrace i \\rbrace = \\lbrace 1, 2 \\rbrace$ is a good set, because $(X_1, X_2, X_3) = (3, 1, -2)$ satisfies the condition in the problem statement, for example, so replace $S$ with $\\lbrace 1, 2\\rbrace$.\n*   For $i = 3$, the set $S \\cup \\lbrace i \\rbrace = \\lbrace 1, 2, 3 \\rbrace$ is not a good set.\n*   For $i = 4$, the set $S \\cup \\lbrace i \\rbrace = \\lbrace 1, 2, 4 \\rbrace$ is a good set, because $(X_1, X_2, X_3) = (3, 1, -2)$ satisfies the condition in the problem statement, for example, so replace $S$ with $\\lbrace 1, 2, 4\\rbrace$.\n*   For $i = 5$, the set $S \\cup \\lbrace i \\rbrace = \\lbrace 1, 2, 4, 5 \\rbrace$ is a good set, because $(X_1, X_2, X_3) = (3, 1, -2)$ satisfies the condition in the problem statement, for example, so replace $S$ with $\\lbrace 1, 2, 4, 5\\rbrace$.\n\nTherefore, the final set $S$ is $\\lbrace 1, 2, 4, 5\\rbrace$."},{"iden":"sample input 2","content":"200000 1\n1 1 1"},{"iden":"sample output 2","content":"The final set $S$ is empty."},{"iden":"sample input 3","content":"5 20\n4 2 125421359\n2 5 -191096267\n3 4 -42422908\n3 5 -180492387\n3 3 174861038\n2 3 -82998451\n3 4 -134761089\n3 1 -57159320\n5 2 191096267\n2 4 -120557647\n4 2 125421359\n2 3 142216401\n4 5 -96172984\n3 5 -108097816\n1 5 -50938496\n1 2 140157771\n5 4 65674908\n4 3 35196193\n4 4 0\n3 4 188711840"},{"iden":"sample output 3","content":"1 2 3 6 8 9 11 14 15 16 17 19"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}