{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"After the ancient apocalypse, the people of the kingdom have started to learn the noble way of living. They proceeded to rebuild their kingdom.\n\nNow, several thousand years after, the kingdom consists of $n$ areas, which are still numbered from $1$ to $n$. Among the areas, $k$ are cities, denoted $c_1, c_2, \\dots, c_k$. The remaining $n - k$ areas are villages.\n\nThe areas are also still connected by $m$ bidirectional roads numbered from $1$ to $m$. The $i$-th road is of length $w_i$ and connects areas $u_i$ and $v_i$. One can always go from one area to another using only the bidirectional roads. Also, there is at most one road connecting any pair of areas.\n\nYou are going to migrate to the kingdom for work. Your work is of high mobility, and involves you going back and forth between two cities frequently. You wonder what is the minimum possible distance between two cities in this kingdom."}},{"title":"Constraints","value":{"format":"MD","content":"- $2 \\leq n \\leq 10^5$\n- $n-1 \\leq m \\leq \\min(3 \\times 10^5, n(n-1)/2)$\n- $1 \\leq u_i, v_i \\leq n, u_i \\neq v_i,$ and $w_i \\leq 10^4$ for $1 \\leq i \\leq m$\n- $2 \\leq k \\leq \\min(n, 10^4)$\n- $1 \\leq c_i \\leq n$ for $1 \\leq i \\leq k$, and $c_i \\neq c_j$ if $i \\neq j$"}},{"title":"Subtasks","value":{"format":"MD","content":"1. (20 points) $n \\leq 300$\n2. (25 points) $m \\leq 10^5$, $k \\leq 10$\n3. (55 points) No additional constraints."}},{"title":"Input","value":{"format":"MD","content":"The first line of the input contains three space-separated integers $n, m,$ and $k$.\n\nThe next line contains $k$ space-separated integers $c_1, c_2, \\dots, c_k$.\n\nThe next $m$ lines each contain three space-separated integers $u_i, v_i,$ and $w_i$."}},{"title":"Output","value":{"format":"MD","content":"Output a single integer denoting the minimum possible distance between two cities in this kingdom."}},{"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\u003e5 5 3\n1 3 5\n1 2 3\n2 3 4\n3 4 1\n4 5 8\n1 5 19\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Note","value":{"format":"MD","content":"The minimum possible distance between two cities in the sample test case is the distance between areas $1$ and $3$."}}]}