วัวของชาวนาจอห์นต้องการที่จะเดินทางไปยังจุด N ( 1 < N < 200 ) จุดบนฟาร์ม แม้ว่าแต่ละจุดจะถูกแบ่งแยกกันด้วยป่า  วัวเหล่านั้นต้องการที่จะเลือกรักษาเส้นทางระหว่างคู่ของจุดเพื่อว่าพวกมันสามารถที่จะเดินทางไปยังจุดใดๆก็ได้บนฟาร์ม   มันสามารถเดินทางบนถนนได้ในทิศทางใดก็ได้

ทุกสัปดาห์ วัวเหล่านี้จะค้นพบเส้นทางใหม่ขึ้น 1 ทาง และมันจะต้องตัดสินใจเลือกรักษาเส้นทางจำนวนหนึ่ง (จากเซตของเส้นทางทั้งหมดที่มันเคยรู้จัก) มาเพื่อที่จะใช้ในสัปดาห์นั้น

วัวเหล่านั้นจะพยายามลดค่าความยาวรวมของถนนที่มันเลือกรักษาให้น้อยที่สุดเท่าที่เป็นไปได้ มันสามารถเลือกที่จะรักษาเซตของเส้นทางใดๆก็ได้ แม้ว่าเส้นทางเหล่านั้นจะไม่ถูกรักษาไว้ในสัปดาห์ก่อน

เส้นทางเหล่านี้ไม่ได้เป็นเส้นตรง ดังนั้นมันไม่แปลกที่วัวจะค้นพบเส้นทางระหว่างคู่จุดเดิมที่มีระยะทางน้อยกว่าเดิม และเส้นทางเหล่านี้อาจจะตัดกันได้ แต่วัวเหล่านี้เป็นวัวที่มุ่งมั่นพวกมันจึงปฏิเสธที่จะเปลี่ยนเส้นทางระหว่างที่มันกำลังเดินอยู่

ในแต่ละสัปดาห์ วัวเหล่านี้จะบอกเส้นทางที่มันได้ค้นพบเพิ่ม  โปรแกรมของคุณจะต้องแสดงค่าความยาวรวมของเส้นทางที่วัวจะต้องรักษาไว้เพื่อว่ามันสามารถเดินทางไปยังจุดใดๆก็ได้บนฟาร์ม

INPUT

บรรทัดแรกประกอบด้วยจำนวนเต็ม N และ W แทนจำนวนจุด และจำนวน สัปดาห์ ( 1 < W < 6000 )

ต่อมา W บรรทัดจะประกอบด้วยจำนวนเต็ม 3 จำนวน โดย 2 จำนวนแรกจะเป็นคู่ของจุดที่เส้นทางนั้นเชื่อม และ Z แทนความยาวของเส้นทางนั้น ( 1 < Z < 10 000 )

OUTPUT

ทันทีหลังจากที่โปรแกรมของคุณรับรู้เส้นทางใหม่ โปรแกรมของคุณจะต้องแสดงจำนวนเต็ม 1 บรรทัดแสดงถึงระยะทางรวมที่น้อยที่สุดของเส้นทางที่วัวเหล่านั้นจะต้องรักษาไว้เพื่อว่ามันสามารถที่จะเดินทางไปยังจุดใดๆก็ได้บนฟาร์ม ถ้าไม่มีเซตของเส้นทางใดที่สามารถทำให้วัวเหล่านั้นเดินทางไปยังทุกจุดได้ ให้แสดง “-1” ออกมาแทน (โดยไม่ต้องมี “”)

ที่มา: International Olympiad In Informatics 2003, USA (http://olympiads.win.tue.nl/ioi/ioi2003/contest/day1/maintain/maintain.pdf)