编程题：快乐暑假

快到暑假了，真得好好放松下。于是小明决定去n个城市旅行。
但是由于手头不宽裕，每个城市他最多只能去两次（当然他需要回到出发城市，但他不介意以哪个城市作为出发点），而且要使得旅游费用最低，所以他向你求助，帮他设计一条合理的路线。

### 输入格式:

输入由多组测试数据组成，直到输入结束；
每组测试数据的第一行是两个整数n(1<=n<=10)和m，表示他要到n个城市旅行，这些城市共有m条道路；之后是m行，表示m条道路的信息，每行包括三个整数 a,b 和 c(1<=a,b<=n)，表示 a 和 b 之间有一条路，花费是 c.

### 输出格式:

输出他需要的最低费用，如果找不到这样的路线，则输出-1。

### 输入样例:

in
2 1
1 2 100
3 2
1 2 40
2 3 50


### 输出样例:

out
100
90







答案：若无答案欢迎评论