King of Destruction

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3002
64-bit integer IO format: %I64d      Java class name: Main

Description

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.

Input

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.

Output

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

Sample Input

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

Sample Output

50
10

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .