Apr23 steiner

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

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

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

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

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

• มีหนึ่งบรรทัดเป็นน้ำหนักของต้นไม้ที่มีทิศทางที่น้อยที่สุด ที่มีโหนด 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