1082 : เกินความจำเป็น (overtree)
Problem type : Batch
Time limit : 1.5 second(s)
Memory limit : 32 megabyte(s)
      การเตรียมงานทุกอย่างเป็นอันเรียบร้อย เหลือเพียงแต่แขกผู้ทรงเกียรติทั้งหลายที่ยังไม่มีใครมาถึงคฤหาสน์แห่งนี้เลยซักคน มีสายโทรศัพท์จากคนขับรถทัวร์มาแจ้งว่า รถทัวร์ที่รับแขกทุกคนมางานเลี้ยงกำลังหลงทางอยู่ในป่าพิศวง!

      เดิมที คนขับรถจะต้องมีแผนที่เส้นทางลัดในป่า ซึ่งมีลักษณะเป็นรูปกราฟต้นไม้ ที่ประกอบไปด้วยจุดพักนักท่องเที่ยว N จุดและถนนเชื่อมระหว่างจุดพักนักท่องเที่ยว N-1 สายซึ่งมีความยาวต่าง ๆ และเป็นถนนแบบ Two-way และเชื่อมจุดพักนักท่องเที่ยวถึงกันได้หมด

      แต่ด้วยความสะเพร่า คนขับรถเจ้าปัญหาได้ลืมแผนที่เส้นทางลัดในป่าไว้ที่บ้าน นั่นทำให้เขาเหลือแต่แผนที่เส้นทางในป่าฉบับเจาะลึก ซึ่งระบุระยะทางระหว่างจุดพักนักท่องเที่ยวต่าง ๆ แทนที่จะระบุถนนที่เชื่อมระหว่างจุดพักนักท่องเที่ยว   ข้อมูลระยะทางที่ระบุในแผนที่ดังกล่าวมีทั้งสิ้น M ข้อมูล แต่ละข้อมูล i จะบอกว่าระหว่างจุดพัก u_i กับ v_i มีระยะทางห่างกัน d_i โดยรับประกันว่า

  • จะมีข้อมูลระยะทางระหว่างเมืองสองเมืองที่มีถนนเชื่อมกันโดยตรง ปรากฏเป็นหนึ่งข้อมูลหนึ่งใน M ข้อมูลนี้เสมอ
  • ระยะทางของถนนระหว่างจุดพักนักท่องเที่ยวใดๆ จะไม่เกิน 10,000 เมตรเสมอ
  • ไม่มีข้อมูลของระยะทางระหว่างคู่จุดพักใด ๆ ที่ปรากฏในข้อมูลนำเข้ามากกว่าหนึ่งครั้ง
      คนขับรถได้วานขอให้คุณช่วยหาถนนในแผนที่เส้นทางลัด ทั้งหมด N-1 เส้น จากข้อมูลระยะทางระหว่างจุดพักนักท่องเที่ยวในแผนที่ฉบับเจาะลึกทั้งสิ้น M ข้อมูลที่กำหนดให้

งานของคุณ
      จงเขียนโปรแกรมรับจำนวนจุดพักนักท่องเที่ยวและข้อมูลระยะทางระหว่างคู่ของจุดพักนักท่องเที่ยวหลายแห่ง แล้วหาว่ามีถนนเส้นใดอยู่ในแผนที่ทางลัดบ้าง

ข้อมูลนำเข้า
      บรรทัดแรกมีจำนวนเต็มบวก N (2≤N≤100,000) แทนจำนวนจุดพักนักท่องเที่ยวทั้งหมดและจำนวนเต็ม M (N-1≤M≤1,000,000) แทนข้อมูลความยาวของระยะทางระหว่างคู่ของจุดพักนักท่องเที่ยว
 อีก M บรรทัดถัดไป จะมีข้อมูลระยะทางระหว่างจุดพักนักท่องเที่ยวสองแห่งในแผนที่ฉบับเจาะลึก  กล่าวคือในบรรทัดที่ i+1 ของข้อมูลนำเข้า โดยที่ 1≤i≤M จะระบุจำนวนเต็ม u_i,v_i,d_i ซึ่งหมายความว่าเส้นทางระหว่างจุดพักนักท่องเที่ยว u_i และ v_i  บนกราฟต้นไม้นี้มีระยะทางเป็น d_i (1≤u_i,v_i≤N และ u_i≠v_i)

ข้อมูลส่งออก
       มี N-1 บรรทัด บอกคู่ของถนนที่ปรากฏในแผนที่เส้นทางลัด บรรทัดละหนึ่งคู่ โดยสามารถแสดงคำตอบในลำดับใดก็ได้

โจทย์โดย: อาภาพงศ์ จันทร์ทอง
ที่มา: TOI.CPP:02-2009
ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5 6
1 2 2
2 3 3
1 4 6
2 4 4
3 5 9
4 5 2
1 2
2 3
2 4
4 5
6 5
1 2 1
2 3 2
3 4 5
4 5 11
5 6 4
1 2
2 3
3 4
4 5
5 6

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 21 ผู้เยี่ยมชมและ 0 สมาชิก (3 บอท)