Sam is a postman of the city X, his job is to deliver mails to their destinations. There are N destinations (labeled from 1 to N), one post office (always labeled with 0), and M streets connecting these destinations and the post office. Every day Sam start from the post office at time 0, carrying all the mails he should deliver on that day, and then deliver them along the streets. When he reaches a destination at the first time, he will hand the mail to the person at that destination immediately.

The dissatisfaction of one person is the time he should wait until he receives his mail. Sam wants to design a route in order to minimize the total dissatisfaction of these N persons.

The first line is an integer T indicating the number of test cases.

Next T block, each block is a test case.

First line of each block is two integers N, M (1 <= N <= 15, 0 <= M <= 200)

Followed by M lines, each line is three integers A B C, indicating that there is a street whose length is C between A and B. (0 <= A, B <= N, 0 < C < 10,000)

If Sam can deliver all these N mails to their destinations output the minimum dissatisfaction, otherwise output -1.

1
3 6
0 1 1
0 2 4
0 3 3
1 2 2
1 3 2
2 3 10

11