{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\n\u003cp\u003e\nThere is a tree that has \u003cvar\u003en\u003c/var\u003e nodes and \u003cvar\u003en-1\u003c/var\u003e edges.\nThere are military bases on \u003cvar\u003et\u003c/var\u003e out of the \u003cvar\u003en\u003c/var\u003e nodes.\nWe want to disconnect the bases as much as possible by destroying \u003cvar\u003ek\u003c/var\u003e edges.\nThe tree will be split into \u003cvar\u003ek+1\u003c/var\u003e regions when we destroy \u003cvar\u003ek\u003c/var\u003e edges.\nGiven the purpose to disconnect the bases, we only consider to split in a way that each of these \u003cvar\u003ek+1\u003c/var\u003e regions has at least one base.\nWhen we destroy an edge, we must pay destroying cost.\nFind the minimum destroying cost to split the tree.\n\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cp\u003e\nThe input consists of multiple data sets.\nEach data set has the following format.\nThe first line consists of three integers \u003cvar\u003en\u003c/var\u003e, \u003cvar\u003et\u003c/var\u003e, and \u003cvar\u003ek\u003c/var\u003e (\u003cvar\u003e1 \\leq n \\leq 10,000\u003c/var\u003e, \u003cvar\u003e1 \\leq t \\leq n\u003c/var\u003e, \u003cvar\u003e0 \\leq k \\leq t-1\u003c/var\u003e).\nEach of the next \u003cvar\u003en-1\u003c/var\u003e lines consists of three integers representing an edge.\nThe first two integers represent node numbers connected by the edge.\nA node number is a positive integer less than or equal to \u003cvar\u003en\u003c/var\u003e.\nThe last one integer represents destroying cost.\nDestroying cost is a non-negative integer less than or equal to 10,000.\nThe next \u003cvar\u003et\u003c/var\u003e lines contain a distinct list of integers one in each line, and represent the list of nodes with bases.\nThe input ends with a line containing three zeros, which should not be processed. \n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003e\nFor each test case, print its case number and the minimum destroying cost to split the tree with the case number.\n\u003c/p\u003e\n\n\u003ch2\u003eSample Input\u003c/h2\u003e\n\n\u003cpre\u003e2 2 1\n1 2 1\n1\n2\n4 3 2\n1 2 1\n1 3 2\n1 4 3\n2\n3\n4\n0 0 0\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input\u003c/h2\u003e\n\n\u003cpre\u003eCase 1: 1\nCase 2: 3\n\u003c/pre\u003e\n"}}]}