รัฐของคุณเพิ่งซื้อผืนดินขนาดใหญ่ที่ยังคงสภาพธรรมชาติ และต้องการเปลี่ยนให้เป็นอุทยานธรรมชาติที่มีเส้นทางเดินป่า ผืนดินนี้มีสถานที่น่าสนใจ $n$ แห่งที่ผู้มาเยือนอาจต้องการเดินไปชม ในจำนวนนี้มีสถานที่พิเศษมาก $k$ แห่ง รัฐต้องการเชื่อมสถานที่เหล่านี้ด้วยเส้นทางเดินป่า มีเส้นทางที่อาจเลือกสร้างได้ $m$ เส้น ซึ่งเชื่อมสถานที่น่าสนใจสองแห่งโดยตรงและมีค่าใช้จ่ายต่างกัน มีข้อจำกัดบางประการในการเลือกเส้นทาง ประการแรก ต้องมีวิธีเดินจากสถานที่ใด ๆ ไปยังสถานที่อื่นใดเพียงวิธีเดียว ประการที่สอง ต้องมีเส้นทางจำนวน $w$ เส้นพอดีที่เชื่อมสถานที่พิเศษกับสถานที่ทั่วไปโดยตรง แน่นอนว่ารัฐต้องการทำให้ค่าใช้จ่ายในการบุกเบิกเส้นทางเหล่านี้ต่ำที่สุด

ข้อมูลนำเข้า

ข้อมูลนำเข้าแต่ละชุดมีกรณีทดสอบเพียงกรณีเดียว โปรดทราบว่าโปรแกรมของคุณอาจถูกเรียกใช้หลายครั้งด้วยข้อมูลนำเข้าที่ต่างกัน บรรทัดแรกมีจำนวนเต็มสี่จำนวน $n$, $m$, $k$ และ $w$ โดย $n$ ($2 \le n \le 2\cdot 10^5$) คือจำนวนสถานที่ $m$ ($1 \le m \le 5\cdot 10^5$) คือจำนวนเส้นทางตรงระหว่างสถานที่ที่อาจสร้างได้ $k$ ($1 \le k < n$) คือจำนวนสถานที่พิเศษ และ $w$ ($1 \le w \le n-1$) คือจำนวนเส้นทางตรงที่เชื่อมสถานที่พิเศษกับสถานที่ที่ไม่พิเศษซึ่งรัฐต้องการบุกเบิก สถานที่มีหมายเลข $1,\ldots,n$

แต่ละบรรทัดใน $k$ บรรทัดถัดไปมีจำนวนเต็มหนึ่งจำนวน $s$ ($1 \le s \le n$) ระบุสถานที่พิเศษ ค่าเหล่านี้ไม่ซ้ำกันและเรียงจากน้อยไปมาก

แต่ละบรรทัดใน $m$ บรรทัดถัดไปอธิบายเส้นทางที่รัฐอาจบุกเบิกได้ แต่ละบรรทัดมีจำนวนเต็มสามจำนวน $a$, $b$ และ $c$ โดยเส้นทางจะเชื่อมสถานที่ $a$ และ $b$ ($1 \le a,b \le n$, $a \ne b$) และมีค่าใช้จ่าย $c$ ($1 \le c \le 10^5$) ระหว่างสถานที่สองแห่งใด ๆ จะมีเส้นทางที่อาจสร้างได้ไม่เกินหนึ่งเส้น และเส้นทางจาก $a$ ไป $b$ ถือเป็นเส้นทางเดียวกับเส้นทางจาก $b$ ไป $a$

ข้อมูลส่งออก

พิมพ์จำนวนเต็มหนึ่งจำนวน ซึ่งเป็นค่าใช้จ่ายรวมต่ำที่สุดที่รัฐต้องใช้เพื่อบุกเบิกเส้นทางในอุทยานแห่งใหม่ภายใต้ข้อจำกัดที่กำหนด หรือพิมพ์ $-1$ หากทำไม่ได้

ตัวอย่าง

ข้อมูลนำเข้า 1

3 3 1 2
2
1 2 2
1 3 1
2 3 3

ข้อมูลส่งออก 1

5

ข้อมูลนำเข้า 2

3 1 1 1
2
1 2 2

ข้อมูลส่งออก 2

-1