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

2108 он гэхэд Миний дэлгүүрийн сүлжээ Монгол орон даяар тархсан байв. Энэ үед Монгол улс n ширхэг аймагт хуваагдсан байсан ба аймаг бүр өөрийн төвтэй болсон байна. Харин аймгуудын төв бүрт Миний дэлгүүрийн нэг салбар байна. Тэдгээр нь хоорондоо бараа тээвэрлэхдээ тийрэлтэт пуужин ашиглана. Аймгийн төвүүдийн хоорондох зайнаас хамааран нэг удаа тийрэлтэт пуужингаар ачаа тээвэрлэх үнэ харилцан адилгүй байна.
Миний дэлгүүрийн захирал Их хуралд сонгогдсон тул Зам тээврийн яамнаас хоорондоо тийрэлтэт пуужингаар тээвэр хийж болох аймгуудын нэрс болон тэдгээрийн бүгдийнх нь үнэ тарифуудыг нууцаар олж авчээ. Ингээд салбар дэлгүүр хоорондын ачаа тээвэрлэлтийн зардлыг багасгахын тулд эдгээр хурдтай тээвэрлэлтүүдээс хэдийг нь сонгон авч хэрэглэхээ сонгох хэрэгтэй болсон байна. Сонгон авсан тээвэрлэлтүүдийг ашиглан аль ч дэлгүүрээс бусад дэлгүүрүүдийг дамжин (эсвэл шууд) бусад бүх дэлгүүрүүд рүү ачаа хүргэж болдог байна. Ийм шинж чанарыг хангасан бөгөөд нийт үнэ нь хамгийн бага байх тээвэрлэлтүүдийг сонговол хамгийн ашигтай сонголт болох байв. Гэвч хамгийн ашигтай хувилбарыг сонговол Зам тээврийн яамнаас нууцаар мэдээлэл авсан нь илэрхий болох тул захирал хамгийн ашигтай хувилбарын дараагийн хувилбарыг сонгон авахаар шийджээ.
Миний дэлгүүрийн захиралд тус болж хамгийн ашигтай ба түүний дараах хувилбаруудын тээвэрлэлтүүдийн үнийн нийт дүнг олох програм бич.

Input

Эхний мөрөнд нийт аймгуудын тоо болох n (2<=n<=500) бүхэл тоо болон пуужингаар хийгддэг тээвэрлэлтийн тоо болох m бүхэл тоо өгөгдөнө. Дараагийн m мөрөнд тээвэрлэлт хийгдэж буй хотуудын дугаар a_i, b_i (1<=a_i, b_i<=n) болон тээвэрлэлтийн үнэ болох w_i (0<= w_i <=1000) тоонууд байрлана. Хэрэв А хотоос Б хот руу тээвэрлэлт хийгддэг бол Б хотоос А хот руу мөн адил зардлаар тээвэрлэлт хийж болдог байна. Дурын хоёр хотын хооронд нэгээс илүүгүй тээвэрлэлт хийгдэнэ. Дурын хотоос бусад хотууд руу шууд эсвэл дамжин өнгөрөх аргаар ачаа хүргэж болдог байна.

Output

Хамгийн ашигтай хувилбарын тээвэрлэлтийн нийт зардал болон түүний дараагийн хувилбарын тээвэрлэлтийн нийт зардлыг нэг нэг мөрөнд хэвлэнэ. Хамгийн ашигтай хувилбар хэд хэд байвал аль нэгийнх нь нийт зардлыг хэвлэнэ. Аль нэг хувилбар нь байх боломжгүй бол -1-ийг хэвлэнэ.

Example

Input:
4 6
1 2 2
2 3 2
3 4 2
4 1 2
1 3 1
2 4 1

Output:
4
4

Input:
3 2
1 2 2
2 3 2

Output:
4
-1