{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003e\r\n\tWith every year, the plans for the construction of motorways in Poland are more \r\n\tand more advanced. For some time, it seemed as if the building was actually \r\n\tgoing to start, so the question of purchasing the land under the roads was of \r\n\tsome importance. Only certain cities can be connected by a road directly, \r\n\tprovided the farmer owning the land under it agrees to sell out. As a result of \r\n\tthe constant swing of moods, the price demanded for the land by each farmer \r\n\tchanges in a linear fashion, with possibly different coefficients for every \r\n\troad. It may either increase or decrease (and sometimes even be negative, if \r\n\tthe owner anticipates future profit from the proximity of a motorway).\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\n\tIt has been decided that the purchase of land will be made at some moment in \r\n\tbetween two fixed dates. At that moment, the current prices of land will be \r\n\tfrozen, and the least costly configuration of bidirectional roads connecting \r\n\tall cities (directly or indirectly) will be chosen. All the land under the \r\n\tselected roads will subsequently be bought at the frozen price. Since business in the proximity of a motorway does have its advantages, some land owners might actually want their land to be bought and they may offer money into the bargain, consequently making the price of purchase negative.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\n\tYou act as an intermediary for the purchase and charge a steady commission, \r\n\tproportional to the total sum of purchase. Oddly enough, when signing the contract you missed the clause about the possibility of the price being negative and now you begin to wonder whether you won\u0027t end up being charged for your own hard work. Since it is one of your tasks to \r\n\tselect the moment of purchase, do so in such a way as to maximise your profit (if this is impossible, at least cut your losses as much as possible).\r\n\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003e\r\n\tThe input begins with the integer t, the number of test cases. Then t test \r\n\tcases follow.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\n\tFor each test case the first line contains two integers n m, denoting the \r\n\tnumber of cities to be connected and the number of available potential \r\n\troads,respectively(1\u0026lt;\u003dn\u0026lt;\u003d 120,1\u0026lt;\u003dm\u0026lt;\u003d820). The next line contains \r\n\ttwo integers t\u003csub\u003e1\u003c/sub\u003e t\u003csub\u003e2\u003c/sub\u003e, which stand for the earliest possible \r\n\tand latest possible moments of purchase (-10000\u0026lt;\u003dt\u003csub\u003e1\u003c/sub\u003e\u0026lt;\u003dt\u003csub\u003e2\u003c/sub\u003e\u0026lt;\u003d10000). \r\n\tEach of the following m lines contains four integers, the i-th being: u\u003csub\u003ei\u003c/sub\u003e\r\n\tv\u003csub\u003ei\u003c/sub\u003e a\u003csub\u003ei\u003c/sub\u003e b\u003csub\u003ei\u003c/sub\u003e, which means that the i-th road \r\n\tconnects city u\u003csub\u003ei\u003c/sub\u003e with city v\u003csub\u003ei\u003c/sub\u003e, and the purchase of the \r\n\tland under it costs b\u003csub\u003ei\u003c/sub\u003e+j*a\u003csub\u003ei\u003c/sub\u003e units of \r\n\tcurrency at moment j (e.g. at moment 0 the land costs b\u003csub\u003ei\u003c/sub\u003e\r\n\tunits). Please note that these integers are chosen from the following ranges: \r\n\t0\u0026lt;\u003du\u003csub\u003ei\u003c/sub\u003e,v\u003csub\u003ei\u003c/sub\u003e\u0026lt;\u003dn-1, -32000\u0026lt;\u003da\u003csub\u003ei\u003c/sub\u003e,b\u003csub\u003ei\u003c/sub\u003e\u0026lt;\u003d32000.\r\n\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003e\r\n\tFor each test case output a line with two floating point numbers, accurate to \r\n\tthree digits after the decimal point. The first represents the moment of \r\n\ttransaction you ought to choose, the second - the total value of the \r\n\ttransaction at that moment. If more than one moment fulfills the conditions of the problem, choose the earliest.\r\n\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e\r\n2\r\n5 6\r\n0 5\r\n1 0 -6 -4\r\n2 0 3 -3\r\n3 0 1 5\r\n3 1 -2 -3\r\n4 1 -3 -2\r\n4 3 -2 -3\r\n5 7\r\n-20 20\r\n1 0 1 2\r\n2 1 -7 4\r\n3 1 -9 0\r\n3 2 4 9\r\n4 1 0 -2\r\n4 2 2 3\r\n4 3 6 -5\r\n\r\n\u003cb\u003e\u003c/b\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n0.000 -13.000\r\n0.111 -1.000\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\n\u003c/div\u003e"}}]}