#2591. 旅行商变形 2

旅行商变形 2

Description

阿克默决定参观nn个城市,他要参观所有城市,不介意哪座城市是他的起点。有mm条道路照常收费,但他不想去一座城市超过两次,想把总费用降到最低。

Format

Input

输入包含几个测试用例,每个测试用例的第1行都包含两个整数n1n10n(1≤n≤10)mm,表示nn个城市、mm条道路。接下来的mm行,每行都包含三个整数aabbc1abnc(1≤a,b≤n),表示在aabb之间有一条道路,费用是cc

Output

对每个测试用例,都单行输出应支付的最低费用,若找不到这样的路线,则输出1-1

Samples

2 1
1 2 100
3 2
1 2 40
2 3 50
3 3
1 2 3
1 3 4
2 3 10
100
90
7

来源

HDU3001