用dp来求最短路，虽然效率低，但是状态的概念方便解决最短路问题中的很多限制，也便于压缩以保存更多信息。
本题要求访问全图，且每个节点不能访问两次以上。所以用一个三进制数保存全图的访问状态(3^10，空间是足够的），用dp[z+bit[j]][j]=dp[z][i]+ct[i][j]就可以表示，从上一状态以i为结束点，转移到把j加入路径末端后的状态(感叹一下位运算的神奇)。
//
// main.cpp
// hdu_3001
//
// Created by Luke on 2016/11/12.
// Copyright © 2016年 Luke. All rights reserved.
// #include <iostream>
#include <cmath>
#include <algorithm> #include <cstdio>
#define N 15
#define zip 70000
#define INF 919900000//原来要开这么大哇
using namespace std;
int n,m;
int ct[N][N];//存边权
int dp[zip][N];//z状态下，以j为终点的路径费用
int bit[];
void addE(int from,int to,int fee);
void ini();
int digit(int num,int pos);//返回压缩后的当前位置状态
int solve()
{
int ans=INF;
for(int z=;z<bit[n];z++)
{
int f=;
for(int j=;j<n;j++)//表示以j结尾，从位置i转移过来
{
int fix=digit(z,j);
if(fix==) continue;
if(fix==) f=;
//if(dp[z][j]==INF) continue;
for(int i=;i<n&&z+bit[j]<bit[n];i++)
dp[z+bit[j]][j]=min(dp[z+bit[j]][j],dp[z][i]+ct[i][j]);
}
if(f)//如果是合法状态，就更新一遍ans
for(int i=;i<n;i++)
ans=min(ans,dp[z][i]);
}
if(ans==INF)
return -;
return ans;
}
int main(int argc, const char * argv[]) {
cin.sync_with_stdio(false);
bit[]=;
for(int i=;i<=;i++)
bit[i]=bit[i-]*;
while(cin>>n>>m)
{
int a,b,c;
ini(); for(int i=;i<m;i++)
cin>>a>>b>>c,addE(a,b,c);
cout<<solve()<<endl;
} return ;
}
void addE(int from,int to,int fee)
{
from--,to--;//为了节约空间，节点从0开始计数
ct[from][to]=ct[to][from]=min(ct[to][from],fee);
}
void ini()
{
for(int i=;i<N;i++)
for(int j=;j<N;j++)
ct[i][j]=INF;
for(int i=;i<zip;i++)
for(int j=;j<N;j++)
{
if(bit[j]==i)
dp[i][j]=;
else
dp[i][j]=INF;
}
}
int digit(int num,int pos)
{
for(int i=;i<pos;i++)
num/=;
return num%;
}