{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cdiv\u003e\n \u0026nbsp;In ICPCCamp, there are \n \u003cem\u003en \u003c/em\u003ecities and \n \u003cem\u003em \u003c/em\u003eunidirectional roads between cities. The \n \u003cem\u003ei\u003c/em\u003e-th road goes from the a\n \u003csub\u003ei\u003c/sub\u003e-th city to the b\n \u003csub\u003ei\u003c/sub\u003e-th city. For each pair of cities \n \u003cem\u003eu \u003c/em\u003eand \n \u003cem\u003ev\u003c/em\u003e, there is at most one road from \n \u003cem\u003eu \u003c/em\u003eto \n \u003cem\u003ev\u003c/em\u003e. \n \u003c/div\u003e \n \u003cdiv\u003e\n As traffic in ICPCCamp is becoming heavier, toll of the roads also varies. At time \n \u003cem\u003et\u003c/em\u003e, one should pay (c\n \u003csub\u003ei\u003c/sub\u003e⋅t+d\n \u003csub\u003ei\u003c/sub\u003e) dollars to travel along the \n \u003cem\u003ei\u003c/em\u003e-th road. \n \u003c/div\u003e \n \u003cdiv\u003e\n Bobo living in the 1-st city would like to go to the n-th city. He wants to know the average money he must spend at least if he starts from city 1 at \n \u003cem\u003et\u003c/em\u003e∈[0,T]. Note that since Bobo\u0027s car is super-fast, traveling on the roads costs him\n \u003cstrong\u003e no time\u003c/strong\u003e. \n \u003c/div\u003e \n \u003cdiv\u003e\n Formally, if \n \u003cem\u003ef(t)\u003c/em\u003e is the minimum money he should pay from city 1 to city \n \u003cem\u003en \u003c/em\u003eat time \n \u003cem\u003et\u003c/em\u003e, Bobo would like to find \n \u003c/div\u003e \n \u003cp\u003e\u003cbr\u003e\u003cspan class\u003d\"math display\"\u003e$$\\frac{∫_0^Tf(t)dt}{T}$$\u003c/span\u003e\u003cbr\u003e\u003c/p\u003e \n \u003cdiv\u003e \n \u003c/div\u003e \n \u003cdiv\u003e \n \u003cimg SRC\u003d\"CDN_BASE_URL/d2dc482219814755fd37603a8e2fd29c?v\u003d1591506898\" width\u003d\"124\" height\u003d\"79\" alt\u003d\"\"\u003e \n \u003c/div\u003e \n \u003cdiv\u003e \n \u003c/div\u003e \n \u003cp\u003e \u003c/p\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n There are about 20 test cases. \n \u003cdiv\u003e\n The first line contains 3 integers n,m,T (2≤n≤10,1≤m≤n(n-1),1≤T≤10\n \u003csup\u003e4\u003c/sup\u003e). \n \u003c/div\u003e \n \u003cdiv\u003e\n The i-th of the following m lines contains 4 integers a\n \u003csub\u003ei\u003c/sub\u003e,b\n \u003csub\u003ei\u003c/sub\u003e,c\n \u003csub\u003ei\u003c/sub\u003e,d\n \u003csub\u003ei\u003c/sub\u003e (1≤a\n \u003csub\u003ei\u003c/sub\u003e,b\n \u003csub\u003ei\u003c/sub\u003e≤n,a\n \u003csub\u003ei\u003c/sub\u003e≠b\n \u003csub\u003ei\u003c/sub\u003e,0≤c\n \u003csub\u003ei\u003c/sub\u003e,d\n \u003csub\u003ei\u003c/sub\u003e≤10\n \u003csup\u003e3\u003c/sup\u003e). \n \u003c/div\u003e \n \u003cdiv\u003e\n It is guaranteed that Bobo is able to drive from city 1 to city n. \n \u003c/div\u003e \n \u003cdiv\u003e \n \u003c/div\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cdiv\u003e\n \u0026nbsp;A floating number denotes the answer. It will be considered correct if its absolute or relative error does not exceed 10\n \u003csup\u003e-6\u003c/sup\u003e. \n \u003c/div\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e3 3 2\n1 2 1 0\n2 3 1 0\n1 3 1 1\n3 3 2\n1 2 1 0\n2 3 1 0\n1 3 0 5\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e1.75000000\n2.00000000\n\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\u003c/body\u003e\n\u003c/html\u003e"}}]}