样例全过，自己造的hack（见代码结尾注释）也过了，但是提交30pts。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int s=0,f=1; char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
	return s*f;
}
const int N=15;
int n,m,x,y,z,p[N][N],dp[N][8000],dic[N][8000][N],minn=1e15;
void _input_(){ // 读入数据+判重边 
	n=read(); m=read();
	if(m==0){
		cout<<0;
		exit(0);
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++)p[i][j]=1e9;
	}
	for(int i=1; i<=m; i++){
		x=read(),y=read(),z=read();
		p[x][y]=p[y][x]=min(p[x][y],z); // 判重边 
	}
}
void _dynamicp_(){ // 动态规划 
	for(int i=1; i<=n; i++){
		for(int j=0; j<(1<<n); j++){
			dp[i][j]=1e9;
			for(int k=1; k<=n; k++){
				dic[i][j][k]=1e9;
			}
		}
		dic[i][(1<<(i-1))][i]=0;
		dp[i][(1<<(i-1))]=0;
		for(int j=0; j<(1<<n); j++){
			for(int k=1; k<=n; k++){
				if(j&(1<<(k-1))) continue;
				for(int r=1; r<=n; r++){
					if(!(j&(1<<(r-1)))) continue;
					// 进行操作
					for(int q=1;q<=n;q++){
						if(q==k)dic[i][j|(1<<(k-1))][k]=min(dic[i][j|(1<<(k-1))][k],dic[i][j][r]+1);
						else dic[i][j|(1<<(k-1))][q]=min(dic[i][j|(1<<(k-1))][q],dic[i][j][q]);
					}
					dp[i][j|(1<<(k-1))]=min(dp[i][j|(1<<(k-1))],dp[i][j]+(dic[i][j][r]+1)*p[r][k]);
				}
			}
		}
		minn=min(minn,dp[i][(1<<n)-1]);
	} 
}

signed main(){
	_input_();
	_dynamicp_();
	cout<<minn;
	return 0;
} 
/*
  3 3
  1 3 1
  2 3 1
  1 2 9999
 */