{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe HERO country is attacked by other country. The intruder is attacking the \n capital so other cities must send supports to the capital. There are some roads \n between the cities and the goods must be transported along the roads.\u003cbr\u003e\n \u003cbr\u003e\n According the length of a road and the weight of the goods, there will be some \n cost during transporting. The cost rate of each road is the ratio of the cost \n to the weight of the goods transporting on the road. It is guaranteed that the \n cost rate is less than 1.\u003cbr\u003e\n \u003cbr\u003e\n On the other hand, every city must wait till all the goods arrive, and then \n transport the arriving goods together with its own goods to the next city. One \n city can only transport the goods to one city.\u003cbr\u003e\n \u003cbr\u003e\n Your task is find the maximum weight of goods which can arrive at the capital.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003e\u003cbr\u003e\n Input\u003c/b\u003e\u003cbr\u003e\n \u003cbr\u003e\n There are several cases. \u003cbr\u003e\n \u003cbr\u003e\n For each case, there are two integers N (2 \u0026lt;\u003d N \u0026lt;\u003d 100) and M in the first \n line, where N is the number of cities including the capital (the capital is \n marked by N, and the other cities are marked from 1 to N-1), and M is the number \n of roads.\u003cbr\u003e\n \u003cbr\u003e\n Then N-1 lines follow. The i-th (1 \u0026lt;\u003d i \u0026lt;\u003d N - 1) line contains a positive \n integer (\u0026lt;\u003d 5000) which represents the weight of goods which the i-th city \n will transport to the capital.\u003cbr\u003e\n \u003cbr\u003e\n The following M lines represent M roads. There are three numbers A, B, and C \n in each line which represent that there is a road between city A and city B, \n and the cost rate of this road is C.\u003cbr\u003e\n \u003cbr\u003e\n Process to the end of the file. \u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003eOutput\u003c/b\u003e\u003cbr\u003e\n \u003cbr\u003e\n For each case, output in one line the maximum weight which can be transported \n to the capital, accurate up to 2 demical places.\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003eSample Input\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e5 6\u003cbr\u003e\n 10\u003cbr\u003e\n 10\u003cbr\u003e\n 10\u003cbr\u003e\n 10\u003cbr\u003e\n 1 3 0\u003cbr\u003e\n 1 4 0\u003cbr\u003e\n 2 3 0\u003cbr\u003e\n 2 4 0\u003cbr\u003e\n 3 5 0\u003cbr\u003e\n 4 5 0\u003c/p\u003e\n\u003cp\u003e\u003cb\u003e\u003cbr\u003e\n Sample Output\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e40.00\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n\u003ci\u003e\n \u003c/i\u003e\u003c/p\u003e\n"}}]}