{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003e\r\nIn the magic land, there is an annual parade hold on each spring.\r\n\u003cbr\u003e\r\n\u003cbr\u003e\r\nThere are \u003cb\u003eN\u003c/b\u003e cities in magic land, and \u003cb\u003eM\u003c/b\u003e directed roads between cities.\r\n\u003cbr\u003e\r\nOn the parade, there will be some(may be 0) heroes travel in this land, for each hero:\r\nHe start at city begin[i], traveling to some cities, and finish at city end[i]. Note that: begin[i] may be equals to end[i], but he must at least moved to another city during this travel. He can go on one road many times, but it will have a cost for each time.\r\n\u003cbr\u003e\r\n\u003cbr\u003e\r\nThe cost of this parade is the sum of these items:\r\n\u003cbr\u003e\r\n1. The sum of costs by traveling on roads. (If a road is passed by k heroes, then it must be count k times.)\r\n\u003cbr\u003e\r\n2. If for a hero, he ended at a city that not equals to his start city, i.e. begin[i] !\u003d end[i], then it will cost \u003cb\u003eC\u003c/b\u003e dollars to move him back to his home.\r\n\u003cbr\u003e\r\n3. If for a city, there is no heroes visited, then we must pay for the citizen \u003cb\u003eC\u003c/b\u003e dollars as compensate.\r\n\u003cbr\u003e\r\n\u003cbr\u003e\r\nThe value of \u003cb\u003eC\u003c/b\u003e may change every year, and we can predict this value in the following \u003cb\u003eK\u003c/b\u003e years. \r\nYour task is: calculate the minimal cost of each year.\r\n\u003cbr\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003e\r\nIn the first line, there are 3 integers: \u003cb\u003eN\u003c/b\u003e, \u003cb\u003eM\u003c/b\u003e and \u003cb\u003eK\u003c/b\u003e.\r\n\u003cbr\u003e\r\nIn the following \u003cb\u003eM\u003c/b\u003e lines:\r\n\u003cbr\u003e\r\nthere will be 3 integers: \u003cb\u003eS[i]\u003c/b\u003e, \u003cb\u003eT[i]\u003c/b\u003e, and \u003cb\u003eV[i]\u003c/b\u003e, describing a directed road from \u003cb\u003eS[i]\u003c/b\u003e to \u003cb\u003eT[i]\u003c/b\u003e, cost \u003cb\u003eV[i]\u003c/b\u003e dollars.\r\n\u003cbr\u003e\r\nIn the next \u003cb\u003eK\u003c/b\u003e lines:\r\nThere will be an integer: \u003cb\u003eC[i]\u003c/b\u003e, describing the value of \u003cb\u003eC\u003c/b\u003e in that year.\r\n\u003cbr\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003e\r\nOutput \u003cb\u003eK\u003c/b\u003e lines:\r\neach line contain an integer, corresponding to the minimal cost of each year.\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n2 \u003c\u003d \u003cb\u003eN\u003c/b\u003e \u003c\u003d 250\r\n\u003cbr\u003e\r\n1 \u003c\u003d \u003cb\u003eM\u003c/b\u003e \u003c\u003d 30000\r\n\u003cbr\u003e\r\n1 \u003c\u003d \u003cb\u003eK\u003c/b\u003e \u003c\u003d 10000\r\n\u003cbr\u003e\r\n\u003cb\u003eS\u003c/b\u003e[i] !\u003d \u003cb\u003eT\u003c/b\u003e[i], 1 \u003c\u003d \u003cb\u003eS\u003c/b\u003e[i], \u003cb\u003eT\u003c/b\u003e[i] \u003c\u003d \u003cb\u003eN\u003c/b\u003e\r\n\u003cbr\u003e\r\n1 \u003c\u003d \u003cb\u003eV\u003c/b\u003e[i] \u003c\u003d 10000\r\n\u003cbr\u003e\r\n1 \u003c\u003d \u003cb\u003eC\u003c/b\u003e \u003c\u003d 10000\r\n\u003cbr\u003e\r\nNote that: there may be more than 1 road between a certain pair of cities.\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\r\n\u003cb\u003eInput:\u003c/b\u003e\r\n6 5 3\r\n1 3 2\r\n2 3 2\r\n3 4 2\r\n4 5 2\r\n4 6 2\r\n1\r\n5\r\n10\r\n\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n6\r\n21\r\n32\r\n\u003c/pre\u003e\r\n\u003cbr\u003e\r\n\u003cb\u003eExplanation\u003c/b\u003e\r\n\u003cbr\u003e\r\nIn the first year, since \u003cb\u003eC\u003c/b\u003e is very small, an optimal solution is: no hero travel, we pay 1 dollar for each city as compensate.\r\n\u003cbr\u003e\r\nIn the second year, an optimal solution is: One hero traveling in the path: 1-\u003e3-\u003e4-\u003e5. We pay 2+2+2\u003d6 dollars for the roads, 5 dollars for taking him back to city 1, and pay 5 dollars for city 2 and 6 as compensate.\r\n\u003cbr\u003e\r\nIn the third year, one optimal solution is: One hero traveling in the path: 1-\u003e3-\u003e4-\u003e5, and another hero traveling in the path: 2-\u003e3-\u003e4-\u003e6.\r\n"}}]}