Apr23 steiner

ให้กราฟ G แบบมีทิศทาง ที่มีโหนด N โหนด (N <= 1 000) มีเส้นเชื่อมที่มีทิศทางและมีน้ำหนัก M เส้น (M <= 50 000) (ระหว่างโหนดคู่หนึ่ง อาจมีเส้นเชื่อมได้มากกว่าหนึ่งเส้น) โหนดในกราฟมีหมายเลข 0, 1, ..., N - 1

ให้เซตของจุดยอด T ที่มีขนาด K (K <= 10) เราต้องการหาต้นไม้ที่มีทิศทาง (arborescence) ที่เป็น subgraph ของ G ที่มีโหนด 0 เป็นโหนดราก และเชื่อมไปยังทุก ๆ โหนดใน T (อาจจะมีโหนดอื่นร่วมด้วยได้) ที่มีน้ำหนักน้อยที่สุด (นิยามน้ำหนักของต้นไม้เท่ากับผลรวมของนำหนักของเส้นเชื่อมในต้นไม้ทั้งหมด)

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

• บรรทัดแรกระบุจำนวนเต็ม N และ M แทนจำนวนโหนดและจำนวนเส้นเชื่อม
• อีก M บรรทัดระบุเส้นเชื่อม โดยระบุจำนวนเต็ม A B และ C เพื่อระบุว่ามีเส้นเชื่อมจากโหนด A ไปยังโหนด B ที่มีน้ำหนัก C
• บรรทัดถัดไประบุจำนวนเต็ม K แทนขนาดของ T
• บรรทัดถัดไประบุจำนวนเต็ม K จำนวน แทนหมายเลขโหนดในเซต T

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

• มีหนึ่งบรรทัดเป็นน้ำหนักของต้นไม้ที่มีทิศทางที่น้อยที่สุด ที่มีโหนด 0 เป็นโหนดรากและมีทุกโหนดใน T

ตัวอย่าง 1

Input:

6 6
0 1 10
1 3 10
3 5 10
0 2 1
2 4 1
4 5 1
2
4 5

Output:

3

ตัวอย่าง 2

Input:

6 6
0 1 10
1 3 10
3 5 10
0 2 1
2 4 1
5 4 1
2
4 5

Output:

31

ตัวอย่าง 3

Input:

5 8
0 1 1
1 2 1
1 3 1
2 0 2
3 0 2
3 2 2
3 4 2
0 4 10
3
1 2 4

Output:

5