Octagon รับผิดชอบสถานที่ที่มีความสำคัญทางยุทธศาสตร์หลายแห่ง เช่น ไซโลขีปนาวุธ เรดาร์ โรงอาหาร สำนักงานทหารผ่านศึก คลังเครื่องแบบ และอื่น ๆ การรักษาความปลอดภัยของเครือข่ายที่เชื่อมต่อสถานที่เหล่านี้สำคัญอย่างยิ่ง แต่ในขณะเดียวกันก็ควรลดภัยคุกคามต่อเครือข่ายนี้ให้เหลือน้อยที่สุด สำหรับถนนสองทิศทางแต่ละสายที่เชื่อมสถานที่ต่างกัน ได้มีการกำหนดสัมประสิทธิ์ภัยคุกคามจากการโจมตี (เรียกสั้น ๆ ว่าสัมประสิทธิ์) Johnny ซึ่งเพิ่งเข้าทำงานกับ Octagon สามารถคำนวณเซตย่อยของถนนที่ทำให้ผลรวมสัมประสิทธิ์ต่ำที่สุดและยังเดินทางระหว่างสถานที่คู่ใด ๆ ได้ แม้กระทั่งตอนกลางดึก เราเรียกถนนที่อยู่ในเซตย่อยเช่นนี้อย่างน้อยหนึ่งเซตว่าถนนสำคัญ

อย่างไรก็ตาม ไม่มีอะไรแน่นอน สัมประสิทธิ์อาจเปลี่ยนแปลงได้ ในการประเมินประจำปี Octagon ตัดสินใจคำนวณค่าสูงสุดของ $x$ สำหรับถนนแต่ละสาย โดยเมื่อกำหนดสัมประสิทธิ์ของถนนนั้นเป็น $x$ (และคงสัมประสิทธิ์อื่นทั้งหมดไว้ตามเดิม) ถนนนั้นจะเป็นถนนสำคัญ งานนี้ถูกมอบหมายให้ Johnny ผู้ซึ่งไม่อาจทำผิดพลาดในเรื่องที่สำคัญเช่นนี้ได้

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

บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็มสองจำนวน $n$ และ $m$ ($1 \le n \le 100\,000$, $n-1 \le m \le 10^6$) คั่นด้วยช่องว่างหนึ่งช่อง ระบุจำนวนสถานที่ภายใต้การดูแลของ Octagon และจำนวนถนนสองทิศทางระหว่างสถานที่เหล่านั้นตามลำดับ สถานที่ถูกกำหนดหมายเลขด้วยจำนวนธรรมชาติต่อเนื่องตั้งแต่ $1$ ถึง $n$

แต่ละบรรทัดใน $m$ บรรทัดถัดไปมีจำนวนเต็มสามจำนวน $a$, $b$ และ $c$ ($1 \le a,b \le n$, $a \ne b$, $0 \le c \le 10^9$) คั่นด้วยช่องว่างหนึ่งช่อง อธิบายถนนสองทิศทางระหว่างสถานที่ $a$ และ $b$ ที่มีสัมประสิทธิ์ $c$ คู่แบบไม่เรียงลำดับ $\{a,b\}$ แต่ละคู่ปรากฏไม่เกินหนึ่งครั้ง

ถนนที่มีอยู่ทำให้สามารถเดินทางระหว่างสถานที่สองแห่งใด ๆ ได้เสมอ

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

ให้พิมพ์ $m$ บรรทัด บรรทัดละหนึ่งสายถนนจากข้อมูลนำเข้า ตามลำดับเดียวกับในข้อมูลนำเข้า ในบรรทัดของถนนแต่ละสาย ให้พิมพ์จำนวนธรรมชาติหนึ่งจำนวนซึ่งเป็นค่าสูงสุดที่เมื่อเปลี่ยนสัมประสิทธิ์ของถนนนั้นเป็นค่านี้ (และคงสัมประสิทธิ์อื่นไว้ตามเดิม) ถนนนั้นจะเป็นถนนสำคัญ ถ้าค่านี้มากกว่า $10^9$ หรือสามารถมีขนาดใหญ่ได้โดยไม่มีขอบเขต ให้พิมพ์ $10^9$

ตัวอย่าง

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

6 7
1 2 2
2 3 1
3 4 0
1 4 3
3 5 20
4 5 8
3 6 14

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

3
3
3
2
8
20
1000000000

หมายเหตุ

เครือข่ายถนนในตัวอย่างมีลักษณะดังนี้: