การเตรียมงานทุกอย่างเป็นอันเรียบร้อย เหลือเพียงแต่แขกผู้ทรงเกียรติทั้งหลายที่ยังไม่มีใครมาถึงคฤหาสน์แห่งนี้เลยซักคน มีสายโทรศัพท์จากคนขับรถทัวร์มาแจ้งว่า รถทัวร์ที่รับแขกทุกคนมางานเลี้ยงกำลังหลงทางอยู่ในป่าพิศวง!

      เดิมที คนขับรถจะต้องมีแผนที่เส้นทางลัดในป่า ซึ่งมีลักษณะเป็นรูปกราฟต้นไม้ ที่ประกอบไปด้วยจุดพักนักท่องเที่ยว 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

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