{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"MD","content":"Today, the Brilliance Contest will be held! The Brilliance Contest is a competitive programming contest for high school students that will be held all across the country.\n\nThe country consists of $n$ regions, each with exactly one contest site where the students will compete. As the regions are quite far away from one another, there is a communication network consisting of $m$ two-way communication channels between pairs of contest sites. All sites are connected via this communication network.\n\nTo be able to hold the contest, each contest site needs to install a virtual machine (with the size of $b$ bytes). This virtual machine is initially installed directly on $s$ contest sites $c_1, c_2, \\dots, c_s$, then broadcast to and installed in all other sites via the communication network.\n\nTo save energy, all communication channels are initially in an idle state and need to be activated to send information. It takes $e_i$ units of energy to activate the communication channel between station $u_i$ and station $v_i$. Once a channel is activated, it takes $1$ energy unit per byte transmitted via this channel.\n\nYour task is to determine the minimum energy units required to install the virtual machine on all contest sites."}},{"title":"Input","value":{"format":"MD","content":"The first line consists of an integer $t$, the number of test cases $(1 \\leq t \\leq 20)$.\n\nEach test case is described by the following lines.\n\n- The first line contains four space-separated integers $n, m, b,$ and $s \\ (1 \\leq s \\leq n \\leq 10^4, 1 \\leq m \\leq \\min(10^6, n(n-1)/2), 1 \\leq b \\leq 10^6)$.\n- The second line contains $s$ space-separated integers $c_i \\ (1 \\leq c_i \\leq n,$ all $c_i$ are distinct$)$.\n- The final $m$ lines each contain three space-separated integers $u_i, v_i,$ and $e_i \\ (1 \\leq u_i, v_i \\leq n, 1 \\leq e_i \\leq 10^6)$.\n\nIt is guaranteed that for all test cases, there exists a configuration such that it is possible to install the virtual machine on all contest sites."}},{"title":"Output","value":{"format":"MD","content":"For each test case, output a single line containing an integer: the minimum energy units required to install the virtual machine on all contest sites."}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e1\n4 6 10 1\n3\n1 2 4\n1 3 8\n1 4 1\n2 3 2\n2 4 5\n3 4 20\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e37\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}