Description

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

Format

Input

输入包含几个测试用例，每个测试用例的第1行都包含两个整数$n（1≤n≤10）$和$m$，表示$n$个城市、$m$条道路。接下来的$m$行，每行都包含三个整数$a$、$b$和$c（1≤a，b≤n）$，表示在$a$和$b$之间有一条道路，费用是$c$。

Output

对每个测试用例，都单行输出应支付的最低费用，若找不到这样的路线，则输出$-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