{"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\u003eBaoBao, one of the most famous monster hunters, wakes up in the middle of Heltion City dominated by monsters. Having troubles remembering what has happened, BaoBao decides to escape from this horrible city as soon as possible. Despite arming no weapon, he luckily puts his hand on a map in his right pocket, which contains valuable information that can possibly help him find a way out.\u003c/p\u003e\n\u003cp\u003eAccording to the map, Heltion City is composed of $n$ spots connected by $m$ undirected paths. Starting from spot 1, BaoBao must head towards any of the $k$ exits of the city to escape, where the $i$-th of them is located at spot $e_i$.\u003c/p\u003e\n\u003cp\u003eHowever, it\u0027s not an easy task for BaoBao to escape since monsters are everywhere in the city! For all $1 \\le i \\le n$, $d_i$ monsters are wandering near the $i$-th spot, so right after BaoBao arrives at that spot, at most $d_i$ paths connecting the spot will be blocked by monsters and are unable for BaoBao to pass. When BaoBao leaves the $i$-th spot, the monsters will go back to their nests and the blocked paths are clear. Of course, if BaoBao comes back to the spot, at most $d_i$ paths will be again blocked by the monsters. The paths blocked each time may differ.\u003c/p\u003e\n\u003cp\u003eAs BaoBao doesn\u0027t know which paths will be blocked, please help him calculate the shortest time he can escape from the city in the worst case.\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$ (about 100), indicating the number of test cases. For each test case:\u003c/p\u003e\n\u003cp\u003eThe first line contains three integers $n$, $m$ and $k$ ($1 \\le n \\le 10^5$, $1 \\le m \\le 10^6$, $1 \\le k \\le n$), indicating the number of spots, the number of undirected paths and the number of exits of the city.\u003c/p\u003e\n\u003cp\u003eThe second line contains $k$ distinct integers $e_1, e_2, \\dots, e_k$ ($1 \\le e_i \\le n$), indicating $k$ exits of Heltion City.\u003c/p\u003e\n\u003cp\u003eThe third line contains $n$ integers $d_1, d_2, \\dots, d_n$ ($0 \\le d_i \\le m$), where $d_i$ indicates the number of monsters at the $i$-th spot.\u003c/p\u003e\n\u003cp\u003eFor the following $m$ lines, the $i$-th line contains three integers $x_i$, $y_i$ and $w_i$ ($1 \\le x_i,y_i \\le n$, $x_i \\neq y_i$, $1 \\le w_i \\le 10^4$), indicating an undirected edge of length $w_i$ connecting spot $x_i$ and $y_i$.\u003c/p\u003e\n\u003cp\u003eIt\u0027s guaranteed that the total sum of $n$ will not exceed $10^6$ and the total sum of $m$ will not exceed $3 \\times 10^6$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each case output one line containing one integer. If BaoBao can get to some exit in the worst case, output the shortest possible time cost; Otherwise if BaoBao cannot get to any exit in the worst case, output \"-1\" (without quotes) instead.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\u003e2\n3 4 1\n3\n1 1 1\n1 2 1\n1 2 2\n2 3 1\n2 3 2\n3 2 2\n2 3\n2 0 0\n1 2 1\n1 3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n"}}]}