วันนี้มหาเศรษฐี Christian ได้เรียนรู้อัลกอริทึม Dijkstra ที่ใช้ศักย์ของ Johnson เขาชอบมากจนตัดสินใจเพิ่มศักย์ให้กราฟโปรดทั้งหมดของเขา Christian มีรสนิยมแปลกมาก เพราะเขาเก็บเฉพาะกราฟมีทิศทางแบบมีน้ำหนักไว้ในห้องลับ

มาทบทวนการทำงานของศักย์กัน จุดยอดแต่ละจุด $v$ จะได้รับศักย์ซึ่งเป็นจำนวนจริง $\varphi(v)$ หากเดิมมีเส้นเชื่อมจาก $u$ ไป $v$ ที่มีน้ำหนัก $w$ น้ำหนักใหม่จะเป็น $w'=w-\varphi(v)+\varphi(u)$

นิยามความแข็งแกร่งของกราฟเป็นค่าน้อยที่สุดของน้ำหนักเส้นเชื่อมทั้งหมด Christian ไม่ต้องการกราฟที่อ่อนแอในห้องของเขา จึงต้องการเลือกศักย์ให้ความแข็งแกร่งของกราฟมีค่ามากที่สุด จงช่วยเขา

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

บรรทัดแรกมีจำนวนเต็มสองจำนวน $n$ ($2\le n\le1000$) และ $m$ ($1\le m\le100\,000$) ซึ่งเป็นจำนวนจุดยอดและเส้นเชื่อมของกราฟโปรดของ Christian แต่ละบรรทัดใน $m$ บรรทัดถัดมามีจำนวนเต็มสามจำนวน $u_i,v_i,w_i$ อธิบายเส้นเชื่อม โดยเป็นจุดเริ่มต้น จุดปลายทาง และน้ำหนักตามลำดับ ($1\le u_i,v_i\le n$, $|w_i|\le10^6$)

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

บรรทัดแรกต้องมีค่าความแข็งแกร่งสูงสุดของกราฟ หากทำให้คำตอบมีค่าใหญ่ได้อย่างไม่จำกัด ให้พิมพ์สตริง “+inf” แทน

หากคำตอบมีค่าจำกัด บรรทัดที่สองต้องมีจำนวนจริง $n$ จำนวน ซึ่งเป็นศักย์ของจุดยอด ค่าสัมบูรณ์ของแต่ละจำนวนต้องไม่เกิน $10^{10}$ คำตอบของคุณต้องต่างจากทั้งคำตอบที่ถูกต้องและคำตอบที่คำนวณจากศักย์ที่คุณให้มาไม่เกิน $10^{-5}$

ตัวอย่าง

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

3 3
1 2 1
2 3 1
3 1 1

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

1.0
0.0 0.0 0.0

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

2 1
1 2 1

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

+inf