ประชาสัมพันธ์พันธบัตร (acm15_bond_tour)


Time limit:
5000 ms
Memory limit:
64 MB

ขณะนี้ปี พ.ศ. 2600 โลกกำลังอยู่ในมหาสงครามครั้งใหญ่ ทั่วโลกต่างมีปัญหาขาดแคลนทั้งเงินและทรัพยากร และประเทศของคุณก็เป็นหนึ่งในนั้น หนึ่งในวิธีหาเงินที่เร็วที่สุดและนิยมใช้กันในเวลาสงครามคือการออกพันธบัตร หรือ bond นั่นเอง

ในประเทศของคุณ มีอยู่ทั้งหมด N เมือง (2 ≤ N ≤ 100,000) และแต่ละเมืองจะมีถนนเชื่อมกัน โดยเมืองทุกเมืองสามารถเดินทางไปหาเมืองอื่นๆ ได้ และรับประกันว่ามีวิธีการเดินทางจากเมืองหนึ่งไปยังอีกเมืองหนึ่งเพียงแค่วิธีเดียวเท่านั้น

รัฐบาลมีแผนจะส่งขบวนเดินประชาสัมพันธ์เกี่ยวกับพันธบัตรนี้ทั้งหมด K ขบวน (10 ≤ K ≤ 100,000) โดยขบวนที่ i จะเดินทางจากเมือง Ai ไปยังเมือง Bi ตามถนน โดยการประชาสัมพันธ์จะเกิดขึ้นขณะเดินบนถนน (เนื่องจากคนเมืองบริจาคจนหมดตัวแล้ว) เนื่องจากข้อจำกัดทางงบประมาณ ทำให้ขบวนประชาสัมพันธ์สามารถทำการประชาสัมพันธ์ได้เพียงช่วงเดียวเท่านั้น กล่าวคือ สมมติเดินทางจากเมือง A → B → C → D (เดินทางจากเมือง A ไป D) จะสามารถประชาสัมพันธ์บนถนนในช่วงเมือง A ถึง D ก็ได้ จะประชาสัมพันธ์บนถนนในช่วงเมือง B ถึง C ก็ได้ แต่ประชาสัมพันธ์บนถนนในช่วงเมือง A ถึง B และอีกครั้งในช่วง C ถึง D ไม่ได้ (คือมีช่วงถนนระหว่างเมือง B ถึง C ที่ไม่ได้ประชาสัมพันธ์) ทั้งนี้ หากไม่มีถนนใดเลยที่ทำให้เงินเพิ่มขึ้น อาจจะไม่มีการประชาสัมพันธ์เลยก็ได้

จากการสำรวจเบื้องต้น พบว่า หากมีการเดินประชาสัมพันธ์พันธบัตรสงครามบนถนนเส้นที่ i จะทำให้ยอดขายพันธบัตรเปลี่ยนแปลงไป wi บาท (-10,000 ≤ wi ≤ 10,000) โดยเลขนี้อาจจะเป็นค่าติดลบ รัฐบาลต้องการทราบว่าสำหรับขบวนประชาสัมพันธ์แต่ละขบวน จะสามารถทำเงินได้มากที่สุดเท่าใด

Input

บรรทัดแรกมีจำนวนเต็ม t (1 ≤ t ≤ 20) แทนจำนวนข้อมูลนำเข้าทั้งหมด โดยในแต่ละชุดข้อมูลนำเข้า:

บรรทัดแรก มีจำนวนเต็ม N K แทนจำนวนเมือง และจำนวนขบวนประชาสัมพันธ์ตามลำดับ

อีก (N-1) บรรทัดต่อมา มีจำนวนเต็มสามจำนวน ai bi wi (0 ≤ ai, bi < N) แทนถนนที่เชื่อมจากเมือง ai ไปเมือง bi และรายได้จากการประชาสัมพันธ์บนถนนเส้นดังกล่าว

อีก K บรรทัดถัดมา มีจำนวนเต็มสามจำนวน Ai Bi แทนการเดินขบวนต่างๆ

Output

สำหรับแต่ละชุดข้อมูลนำเข้า มี K บรรทัด แต่ละบรรทัดแสดงการรายได้จากการขายพันธบัตรในแต่ละขบวนประชาสัมพันธ์

Editor:

Source: ACM ICPC 2015 Thailand Local Central Group B

Select description language

Thai (raw)
English (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None