{"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, một trong những thợ săn quái vật nổi tiếng nhất, tỉnh dậy giữa thành phố Heltion bị quái vật chiếm đóng. Gặp khó khăn trong việc nhớ lại những gì đã xảy ra, BaoBao quyết định trốn thoát khỏi thành phố kinh hoàng này càng sớm càng tốt. Mặc dù không mang theo vũ khí, may mắn thay anh ấy tìm thấy một bản đồ trong túi phải, chứa thông tin quý giá có thể giúp anh ấy tìm đường thoát ra.\u003c/p\u003e\n\u003cp\u003eTheo bản đồ, thành phố Heltion được tạo thành từ $n$ điểm được kết nối bởi $m$ đường đi không hướng. Bắt đầu từ điểm 1, BaoBao phải đi đến bất kỳ một trong $k$ lối ra của thành phố để trốn thoát, trong đó lối ra thứ $i$ nằm tại điểm $e_i$.\u003c/p\u003e\n\u003cp\u003eTuy nhiên, việc trốn thoát không dễ dàng cho BaoBao vì quái vật đang ở khắp nơi trong thành phố! Đối với mỗi $1 \\le i \\le n$, có $d_i$ quái vật lang thang gần điểm thứ $i$, vì vậy ngay sau khi BaoBao đến điểm đó, tối đa $d_i$ đường đi kết nối điểm đó sẽ bị quái vật chặn và không thể đi qua. Khi BaoBao rời khỏi điểm thứ $i$, quái vật sẽ quay trở lại tổ của chúng và các đường bị chặn sẽ được mở lại. Tất nhiên, nếu BaoBao quay trở lại điểm đó, tối đa $d_i$ đường sẽ lại bị quái vật chặn. Các đường bị chặn mỗi lần có thể khác nhau.\u003c/p\u003e\n\u003cp\u003eVì BaoBao không biết những đường nào sẽ bị chặn, hãy giúp anh ấy tính thời gian ngắn nhất mà anh ấy có thể trốn thoát khỏi thành phố trong trường hợp xấu nhất.\u003c/p\u003e\n\n\u003ch4\u003eNhập\u003c/h4\u003e\n\u003cp\u003eCó nhiều bài kiểm tra. Dòng đầu tiên của đầu vào chứa một số nguyên $T$ (khoảng 100), cho biết số lượng bài kiểm tra. Đối với mỗi bài kiểm tra:\u003c/p\u003e\n\u003cp\u003eDòng đầu tiên chứa ba số nguyên $n$, $m$ và $k$ ($1 \\le n \\le 10^5$, $1 \\le m \\le 10^6$, $1 \\le k \\le n$), cho biết số lượng điểm, số lượng đường đi không hướng và số lượng lối ra của thành phố.\u003c/p\u003e\n\u003cp\u003eDòng thứ hai chứa $k$ số nguyên phân biệt $e_1, e_2, \\dots, e_k$ ($1 \\le e_i \\le n$), cho biết $k$ lối ra của thành phố Heltion.\u003c/p\u003e\n\u003cp\u003eDòng thứ ba chứa $n$ số nguyên $d_1, d_2, \\dots, d_n$ ($0 \\le d_i \\le m$), trong đó $d_i$ chỉ ra số lượng quái vật tại điểm thứ $i$.\u003c/p\u003e\n\u003cp\u003eĐối với $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $x_i$, $y_i$ và $w_i$ ($1 \\le x_i,y_i \\le n$, $x_i \\neq y_i$, $1 \\le w_i \\le 10^4$), cho biết một cạnh không hướng có độ dài $w_i$ nối giữa điểm $x_i$ và $y_i$.\u003c/p\u003e\n\u003cp\u003eĐảm bảo rằng tổng của $n$ sẽ không vượt quá $10^6$ và tổng của $m$ sẽ không vượt quá $3 \\times 10^6$.\u003c/p\u003e\n\n\u003ch4\u003eXuất\u003c/h4\u003e\n\u003cp\u003eĐối với mỗi trường hợp, xuất ra một dòng chứa một số nguyên. Nếu BaoBao có thể đến một lối ra trong trường hợp xấu nhất, xuất ra thời gian tối thiểu có thể; Nếu không thể đến bất kỳ lối ra nào trong trường hợp xấu nhất, xuất ra \"-1\" (không có dấu ngoặc) thay vì.\u003c/p\u003e\n\n\u003ch4\u003eVí dụ\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"}}]}