{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAs the current heir of a wizarding family with a long history,unfortunately, you find yourself forced to participate in the cruel Holy Grail War which has a reincarnation of sixty years.However,fortunately,you summoned a Caster Servant with a powerful Noble Phantasm.When your servant launch her Noble Phantasm,it will construct a magic field,which is actually a \u003cstrong\u003edirected\u003c/strong\u003e \u003cstrong\u003egraph\u003c/strong\u003e consisting of \u003cstrong\u003en vertices\u003c/strong\u003e and \u003cstrong\u003em edges\u003c/strong\u003e.More specifically,the graph satisfies the following restrictions :\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003eDoes not have multiple edges(for each pair of vertices \u003cstrong\u003e\u003cem\u003ex\u003c/em\u003e\u003c/strong\u003e and \u003cstrong\u003e\u003cem\u003ey\u003c/em\u003e\u003c/strong\u003e, there is at most one edge between this pair of vertices in the graph) and does not have self-loops(edges connecting the vertex with itself).\u003c/li\u003e\n \u003cli\u003eMay have \u003cstrong\u003enegative-weighted edges\u003c/strong\u003e.\u003c/li\u003e\n \u003cli\u003eDoes not have a \u003cstrong\u003enegative-weighted loop\u003c/strong\u003e.\u003c/li\u003e\n \u003cli\u003e\u003cstrong\u003en\u0026lt;\u003d300\u003c/strong\u003e , \u003cstrong\u003em\u0026lt;\u003d500\u003c/strong\u003e.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eCurrently,as your servant\u0027s Master,as long as you add extra \u003cstrong\u003e6\u003c/strong\u003e edges to the graph,you will beat the other 6 masters to win the Holy Grail.\u003c/p\u003e\n\u003cp\u003eHowever,you are subject to the following restrictions when you add the edges to the graph:\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003eEach time you add an edge whose cost is c,it will cost you c units of Magic Value.Therefore,you need to add an edge which has the lowest weight(it\u0027s probably that you need to add an edge which has a negative weight).\u003c/li\u003e\n \u003cli\u003eEach time you add an edge to the graph,the graph must not have negative loops,otherwise you will be engulfed by the Holy Grail you summon.\u003c/li\u003e\n\u003c/ul\u003e\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003eInput data contains multiple test cases. The first line of input contains integer \u003cstrong\u003et\u003c/strong\u003e — the number of testcases ($1 \\le t \\le 5$).\u003c/p\u003e\n\u003cp\u003eFor each test case,the first line contains two integers n,m,the number of vertices in the graph, the initial number of edges in the graph.\u003c/p\u003e\n\u003cp\u003eThen m lines follow, each line contains three integers \u003cstrong\u003ex, y and w\u003c/strong\u003e (\u003cstrong\u003e$0 \\le x,y\u0026lt;n$\u003c/strong\u003e,$-10^9$≤w≤$10^9$, $x \\not \u003d y$) denoting an edge from vertices x to y (\u003cstrong\u003e0-indexed\u003c/strong\u003e) of weight w.\u003c/p\u003e\n\u003cp\u003eThen 6 lines follow, each line contains two integers \u003cstrong\u003es,t\u003c/strong\u003e denoting \u003cstrong\u003ethe starting vertex\u003c/strong\u003e and \u003cstrong\u003ethe ending vertex\u003c/strong\u003e of the edge you need to add to the graph.\u003c/p\u003e\n\u003cp\u003eIt is guaranteed that there is not an edge starting from \u003cstrong\u003es to t\u003c/strong\u003e before you add any edges and there must exists such an edge which has the lowest weight and satisfies the above restrictions, meaning the solution absolutely exists for each query.\u003c/p\u003e\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eFor each test case,output $6$ lines.\u003c/p\u003e\n\u003cp\u003eEach line contains the weight of the edge you add to the graph.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n10 15\n4 7 10\n7 6 3\n5 3 3\n1 4 11\n0 6 20\n9 8 25\n3 0 9\n1 2 15\n9 0 27\n5 2 0\n7 3 -5\n1 7 21\n5 0 1\n9 3 16\n1 8 4\n4 1\n0 3\n6 9\n2 1\n8 7\n0 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-11\n-9\n-45\n-15\n17\n7\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}