Language: C++

/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=15;
int n,m;
int tb[N][N];
int sum[1<<N];
int tmp[1<<N][N],dp[1<<N][N];
void prt_bitmsk(int x){
	for(int i=0;i<n;i++)cout<<!!(x&1<<i);
}
int main(){
	cin>>n>>m;
	int tot=0;
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		x--;y--;
		tb[x][y]=tb[y][x]=z;
		tot+=z;
	}
	for(int i=0;i<1<<n;i++){
		for(int j=0;j<n;j++)if(i&1<<j)for(int k=j+1;k<n;k++)if(i&1<<k)
			sum[i]+=tb[j][k];
//		printf("sum[");prt_bitmsk(i);printf("]=%d\n",sum[i]);
	}
	for(int i=0;i<1<<n;i++)for(int j=0;j<n;j++)dp[i][j]=tmp[i][j]=-inf;
	int mx=-inf;
	for(int i=0;i<1<<n;i++)if(i&1)for(int j=0;j<n;j++)if(i&1<<j){
		if(j)
			for(int k=i^1<<j^1;;k=k-1&(i^1<<j^1)){
				dp[i][j]=max(dp[i][j],sum[k|1<<j]+tmp[i^k^1<<j][j]);
				if(!k)break;
			}
		else
			dp[i][j]=sum[i];
//		printf("dp[");prt_bitmsk(i);printf("][%d]=%d\n",j,dp[i][j]);
		for(int k=0;k<n;k++)if(!(i&1<<k))
			if(tb[j][k])
				tmp[i][k]=max(tmp[i][k],dp[i][j]+tb[j][k]);
	}
	cout<<tot-dp[(1<<n)-1][n-1];
	return 0;
}
/*1
4 6
1 2 100
3 1 100
2 4 100
4 3 100
1 4 100
3 2 100
*/
/*2
2 1
1 2 1
*/
/*3
15 22
8 13 33418
14 15 55849
7 10 15207
4 6 64328
6 9 86902
15 7 46978
8 14 53526
1 2 8720
14 12 37748
8 3 61543
6 5 32425
4 11 20932
3 12 55123
8 2 45333
9 12 77796
3 9 71922
12 15 70793
2 4 25485
11 6 1436
2 7 81563
7 11 97843
3 1 40491
*/
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=15;
int n,m;
int tb[N][N];
int sum[1<<N];
int tmp[1<<N][N],dp[1<<N][N];
void prt_bitmsk(int x){
	for(int i=0;i<n;i++)cout<<!!(x&1<<i);
}
int main(){
	cin>>n>>m;
	int tot=0;
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		x--;y--;
		tb[x][y]=tb[y][x]=z;
		tot+=z;
	}
	for(int i=0;i<1<<n;i++){
		for(int j=0;j<n;j++)if(i&1<<j)for(int k=j+1;k<n;k++)if(i&1<<k)
			sum[i]+=tb[j][k];
//		printf("sum[");prt_bitmsk(i);printf("]=%d\n",sum[i]);
	}
	for(int i=0;i<1<<n;i++)for(int j=0;j<n;j++)dp[i][j]=tmp[i][j]=-inf;
	int mx=-inf;
	for(int i=0;i<1<<n;i++)if(i&1)for(int j=0;j<n;j++)if(i&1<<j){
		if(j)
			for(int k=i^1<<j^1;;k=k-1&(i^1<<j^1)){
				dp[i][j]=max(dp[i][j],sum[k|1<<j]+tmp[i^k^1<<j][j]);
				if(!k)break;
			}
		else
			dp[i][j]=sum[i];
//		printf("dp[");prt_bitmsk(i);printf("][%d]=%d\n",j,dp[i][j]);
		if(j==n-1)mx=max(mx,dp[i][j]);
		for(int k=0;k<n;k++)if(!(i&1<<k))
			if(tb[j][k])
				tmp[i][k]=max(tmp[i][k],dp[i][j]+tb[j][k]);
	}
	cout<<tot-mx;
	return 0;
}
/*1
4 6
1 2 100
3 1 100
2 4 100
4 3 100
1 4 100
3 2 100
*/
/*2
2 1
1 2 1
*/
/*3
15 22
8 13 33418
14 15 55849
7 10 15207
4 6 64328
6 9 86902
15 7 46978
8 14 53526
1 2 8720
14 12 37748
8 3 61543
6 5 32425
4 11 20932
3 12 55123
8 2 45333
9 12 77796
3 9 71922
12 15 70793
2 4 25485
11 6 1436
2 7 81563
7 11 97843
3 1 40491
*/

Compiler output:
a.cc:95:1: error: extended character 。 is not valid in an identifier
   95 | 多测不读完，爆零两行泪。
      | ^
a.cc:96:1: error: extended character 。 is not valid in an identifier
   96 | 边界不特判，爆零两行泪。
      | ^
a.cc:97:1: error: extended character 。 is not valid in an identifier
   97 | 贪心不证明，爆零两行泪。
      | ^
a.cc:98:5: error: extended character 。 is not valid in an identifier
   98 | D P 顺序错，爆零两行泪。
      |     ^
a.cc:99:1: error: extended character 。 is not valid in an identifier
   99 | 大小少等号，爆零两行泪。
      | ^
a.cc:100:1: error: extended character 。 is not valid in an identifier
  100 | 变量不统一，爆零两行泪。
      | ^
a.cc:101:1: error: extended character 。 is not valid in an identifier
  101 | 越界不判断，爆零两行泪。
      | ^
a.cc:102:1: error: extended character 。 is not valid in an identifier
  102 | 调试不注释，爆零两行泪。
      | ^
a.cc:103:10: error: extended character 。 is not valid in an identifier
  103 | 溢出不 l l，爆零两行泪。
      |          ^
a.cc:95:1: error: '\U0000591a\U00006d4b\U00004e0d\U00008bfb\U00005b8c\U0000ff0c\U00007206\U000096f6\U00004e24\U0000884c\U00006cea\U00003002' does not name a type
   95 | 多测不读完，爆零两行泪。
      | ^~~~~~~~~~~~~~~~~~~~~~~~
a.cc:107:11: error: redefinition of 'const int inf'
  107 | const int inf=0x3f3f3f3f;
      |           ^~~
a.cc:15:11: note: 'const int inf' previously defined here
   15 | const int inf=0x3f3f3f3f;
      |           ^~~
a.cc:108:11: error: redefinition of 'const int N'
  108 | const int N=15;
      |           ^
a.cc:16:11: note: 'const int N' previously defined here
   16 | const int N=15;
      |           ^
a.cc:109:5: error: redefinition of 'int n'
  109 | int n,m;
      |     ^
a.cc:17:5: note: 'int n' previously declared here
   17 | int n,m;
      |     ^
a.cc:109:7: error: redefinition of 'int m'
  109 | int n,m;
      |       ^
a.cc:17:7: note: 'int m' previously declared here
   17 | int n,m;
      |       ^
a.cc:110:5: error: redefinition of 'int tb [15][15]'
  110 | int tb[N][N];
      |     ^~
a.cc:18:5: note: 'int tb [15][15]' previously declared here
   18 | int tb[N][N];
      |     ^~
a.cc:111:5: error: redefinition of 'int sum [32768]'
  111 | int sum[1<<N];
      |     ^~~
a.cc:19:5: note: 'int sum [32768]' previously declared here
   19 | int sum[1<<N];
      |     ^~~
a.cc:112:5: error: redefinition of 'int tmp [32768][15]'
  112 | int tmp[1<<N][N],dp[1<<N][N];
      |     ^~~
a.cc:20:5: note: 'int tmp [32768][15]' previously declared here
   20 | int tmp[1<<N][N],dp[1<<N][N];
      |     ^~~
a.cc:112:18: error: redefinition of 'int dp [32768][15]'
  112 | int tmp[1<<N][N],dp[1<<N][N];
      |                  ^~
a.cc:20:18: note: 'int dp [32768][15]' previously declared here
   20 | int tmp[1<<N][N],dp[1<<N][N];
      |                  ^~
a.cc:113:6: error: redefinition of 'void prt_bitmsk(int)'
  113 | void prt_bitmsk(int x){
      |      ^~~~~~~~~~
a.cc:21:6: note: 'void prt_bitmsk(int)' previously defined here
   21 | void prt_bitmsk(int x){
      |      ^~~~~~~~~~
a.cc:116:5: error: redefinition of 'int main()'
  116 | int main(){
      |     ^~~~
a.cc:24:5: note: 'int main()' previously defined here
   24 | int main(){
      |     ^~~~