Програмчлалын олимпиадын бодлогын архив

Нейрон нь мэдрэлийн эсүүд болон тэдгээрийн хооронд мэдээлэл дамжуулах сувгуудаас тогтоно. Тэдгээр нь хэд хэдэн давхаргуудаас тогтох бөгөөд эхний ба сүүлийн давхарга нь нэг нэг эсээс тогтоно. Эхний ба сүүлийн давхаргуудын хооронд мэдээлэл дамжих боломжтой байдаг байна. Нэг эсээс нөгөө эс рүү сувгаар дамжих мэдээлэл нь хэмжээтэй. Тэгвэл эхний давхаргаас сүүлийн давхарга хүртэл мэдээлэл хүрч болдоггүй байхаар сувгуудыг хасахдаа хассан сувгуудын нийт мэдээллийн хэмжээ нь хамгийн бага байх програм зохио.

Input

Оролт нь 5-аас илүүгүй тест агуулах ба тестийн бүтэц дараах хэлбэртэй байна. Эхний мөрөнд мэдрэлийн эсийн тоо N<=125 болон мэдээлэл дамжуулах сувгуудын нийт тоо M<=300 гэсэн тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана. Дараагийн М мөр тус бүрт A B W тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана. Үүнд: А, B тоонууд нь мэдрэлийн эсийн дугаарууд W (0<=10000 натурал тоо) нь мэдээллийг дамжуулах хэмжээ болно. A-гаас B-д мэдээлэл дамждаг байхад B-гээс A-д мэдээлэл дамжихгүй. Мөн эхний давхарга болон сүүлийн давхарга дахь эсийн дугаар нь 0 ба N-1 байна. Тестийн төгсгөлд N=0 M=0 байна.

Output

Гаралтанд тест бүрд харгалзах хассан сувгуудын нийт мэдээллийн хэмжээний хамгийн бага утгууд нэг нэг мөрөнд байрлана.

Example

Input:
7 8
 0 1 2
 0 2 1
 1 3 3
 2 3 5
 2 4 4
 3 6 2
 4 5 2
 5 6 3
 4 4
 0 1 3
 0 2 4
 1 3 5
 2 3 2
 0 0
 


Output:
3
 5