21787_KingofDestruction

Zhou xingxing is the successor of one style of kung fu called "Karate Kid". he is falling love with a beautiful judo student, after being humiliated by her boyfriend, a Taekwando master from Japan, Zhou is going to fight with his rival in love. The way they fight is to destroy the wooden plank between some wooden pegs, in order to cut these wooden pegs into two disconnected parts, and destroy each piece of plank need consume different energy. However Zhou xingxing is beginner after all, so he is turn to you for help, please calculate the minimum energy he need to destroy the wooden plank.

The input consists of multiple test cases.

Each test case starts with two integers n ( 0 < n ≤ 100 ) and m in one line, where n, m are the number of wooden pegs and wooden plank.

Following are m lines, each line contains three integers s, e and q ( 0 ≤ s, e < n,  q > 0 ), meaning that there need q energy to destroy the wooden plank between s and e.

There is only one line for each test case, which contains the minimum energy they need to complete this fight.

2 1
0 1 50
3 2
0 1 50
1 2 10

50
10