#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define Linf 0x3f3f3f3f3f3f3f3f
#define re register
const int N = 14, S = (1<<12) + 2;
int n, m;
int g[N][N];

int dp[N][S], cost[S][S];	//dp[i][s]：树高（距起点）为i，当前点集为S的生成树的最小代价


void test() {
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) std::cout << dp[i][j] << ' ';
		std::cout<<'\n';	}
}
int main() {
	memset(g, 0x3f, sizeof(g));
	scanf("%d%d", &n, &m);
	for(re int i = 1, u, v, w; i <= m; ++i) {
		scanf("%d%d%d", &u, &v, &w);
		g[u][v] = g[v][u] = std::min(w, g[u][v]);
	}
	
	for(re int s = 0; s < 1 << n; ++s)
		for(re int s0 = s; ; s0 = s0-1 & s) {	//枚举s的子集，预处理从s0加边到s的
			re int ok = 1, t = s ^ s0;	//t为s0关于s的补集，即s-s0
			for(re int i = 1; i <= n; ++i) 
				if(t & 1 << i-1) {
					re int mn = inf;
					for(int j = 1; j <= n; ++j)
						if(s0 & 1 << j-1) mn = std::min(mn, g[j][i]);
					if(mn == inf) {ok = 0; break;}	//无法转移
					cost[s0][s] += mn, t ^= 1 << i-1;	//转移成功一个点，加上代价减去被转移的点
				}
			if(ok == 0) cost[s0][s] = inf;
			if(s0 == 0) break;
		}
	
	memset(dp, 0x3f, sizeof(dp));
	for(re int i = 1; i <= n; ++i) dp[i][1 << i-1] = 0;	//边界：加起点，状态值为0
	for(re int i = 2; i <= n; ++i)
		for(re int s = 0; s < 1 << n; ++s)	//枚举点集
			for(re int s0 = s; ; s0 = s0-1 & s) {	//枚举s的子集
				if(cost[s0][s] != inf) dp[i][s] = std::min(dp[i][s], dp[i-1][s0] + (i-1)*cost[s0][s]);
				if(s0 == 0) break;
			}
	
	int ans = inf;
	for(re int i = 1; i <= n; ++i) ans = std::min(ans, dp[i][(1<<n) - 1]);	//枚举所有可能的树高
	printf("%d", ans);
    return 0;
}

附样例：

in:
12 1000
1 3 31284
1 4 20383
1 5 8838
1 8 19824
2 1 14667
2 2 13845
2 8 13113
2 12 316
3 2 27293
3 7 12035
3 10 8193
3 12 2557
4 8 30064
5 3 3595
5 9 31139
5 10 173
6 3 31276
6 4 2537
6 6 32119
6 8 17147
7 1 32165
7 2 21052
7 10 2100
8 2 12431
8 7 20058
8 8 7832
8 10 23541
8 11 29426
9 1 14934
9 3 10959
9 9 24689
10 5 2338
10 8 5932
10 11 24870
11 1 6368
11 2 7523
11 9 24633
12 1 7320
12 2 11847
12 3 26922
12 4 24857
12 5 32423
12 6 29850
12 7 24078
12 8 13015
12 11 16292
2 5 7126
12 4 8480
7 6 6169
4 3 30971
7 6 12857
12 5 17543
4 3 12939
1 10 11083
5 1 24174
11 7 29764
9 8 4029
8 8 15538
10 8 20379
4 1 16734
1 3 6889
4 6 20230
5 9 16629
11 5 6642
12 7 15688
5 5 26090
3 8 5026
5 8 24312
6 9 8578
12 1 6337
12 5 6862
3 12 11608
12 3 3954
10 8 13783
1 6 30224
10 9 9772
2 12 23582
1 6 17101
4 7 5630
1 7 16982
1 11 10741
4 2 1605
2 9 18190
12 11 32069
7 4 30026
2 10 1742
12 8 24239
12 12 25347
11 1 10512
1 7 11026
10 12 26279
4 5 19843
1 6 14295
3 4 26429
8 3 25263
10 8 23848
10 12 29958
8 11 9136
7 7 3148
9 9 30872
4 3 10842
2 3 18662
7 10 8432
2 8 24514
2 10 9631
10 12 7333
9 6 7760
8 11 7725
1 2 15020
9 1 23657
11 10 2311
1 4 26755
10 2 30116
10 5 16653
9 3 6507
6 10 12637
10 1 31082
4 12 22458
2 10 27311
11 10 335
2 4 18021
10 7 23572
12 3 2106
7 3 24118
5 10 25973
5 6 32675
1 5 30022
1 5 19905
3 2 13108
11 12 19071
7 3 2747
3 7 16189
8 4 18289
6 8 319
9 2 18253
2 12 26789
4 7 13545
12 6 15394
6 1 28115
7 4 25321
12 1 7495
12 4 7038
11 2 3562
9 11 4477
9 12 21854
3 3 17769
12 10 21194
11 9 8485
8 12 5541
8 10 6310
7 11 13415
7 3 10750
9 9 29426
1 1 16594
7 7 26315
3 1 16592
1 11 7034
12 8 6095
2 12 9138
7 9 915
2 11 5129
9 1 111
3 2 10855
4 11 27966
9 12 29053
12 12 9828
3 9 4573
12 1 31959
6 6 19080
2 10 20327
6 5 18705
2 1 31671
10 2 23974
7 8 10663
8 10 24990
4 12 28445
6 7 10075
7 9 17267
11 8 161
2 6 245
6 3 25777
2 5 6187
11 10 4558
4 5 27626
1 1 15857
12 4 24163
9 5 6355
3 6 13993
4 2 5536
10 11 857
5 4 15596
1 2 19063
4 1 14268
1 2 32665
11 1 27335
11 7 12533
11 12 25912
12 10 28910
7 3 10393
3 9 1329
2 4 30644
8 11 9611
8 10 30849
10 4 25584
8 5 6529
10 4 1145
6 3 25884
6 4 26427
6 10 19923
10 2 32579
2 2 5224
11 4 31015
7 2 17736
2 7 30944
6 4 31965
7 10 2537
6 11 15001
8 5 19936
1 9 6345
4 2 29977
6 6 21406
12 3 27098
9 8 13292
1 5 8772
8 8 17031
12 10 5652
3 4 12116
12 9 11448
4 7 9048
6 6 28020
3 12 22393
11 2 7819
1 8 20902
8 6 8614
8 2 10395
1 3 2796
1 12 12943
9 1 32142
5 1 7515
3 9 5038
9 9 12031
11 3 20720
9 8 25496
11 3 9746
9 7 23072
11 8 12637
5 5 5004
7 4 31443
11 3 34
1 8 15456
11 6 17702
9 1 9591
4 11 6444
9 3 18153
1 10 8105
5 2 16084
7 6 23713
6 1 9721
3 11 16261
8 3 30432
5 5 28823
9 9 31886
6 3 3700
9 2 6589
6 3 29076
12 10 15056
6 8 27096
9 4 21507
2 5 20106
12 7 14973
1 4 13140
12 8 16976
10 5 13589
12 12 9362
4 5 10153
4 11 6157
12 8 2547
7 4 3130
10 9 6098
4 9 27010
5 6 10692
3 12 27387
7 1 24673
2 3 25884
10 9 28162
7 12 27166
7 8 15132
9 10 2045
1 9 12866
7 1 9566
8 9 18131
2 3 6596
9 11 21932
6 7 21205
4 5 24963
8 3 31646
3 3 29879
9 4 31778
2 11 12464
2 1 5773
3 3 22313
2 5 13534
10 8 29695
8 6 29943
2 1 20047
7 4 31297
12 7 32274
12 8 21361
5 12 32632
12 6 10256
10 12 28583
11 3 13516
3 6 22199
6 2 11977
9 11 4339
3 12 17760
11 1 7640
8 5 30481
2 11 25916
12 11 6552
1 4 29602
10 11 7773
12 12 21685
10 11 5054
6 4 8015
6 11 30943
12 6 2206
8 8 32008
12 2 31816
3 3 1203
8 4 21914
2 12 7649
7 7 31268
9 7 14922
9 1 20563
7 1 24956
4 5 27875
9 11 26134
11 12 26699
11 3 20630
12 12 10599
11 10 30582
1 5 9477
7 9 28555
10 2 10803
5 9 28899
10 2 24916
9 4 19355
4 2 14438
10 11 25947
6 7 8450
1 11 17277
12 4 21753
9 10 12046
12 6 23716
5 9 22308
12 4 24119
2 2 19271
8 10 24508
10 5 2769
2 8 11645
10 8 1948
8 7 5391
3 3 10585
6 11 10548
7 10 27736
12 6 23880
10 7 29111
1 6 1803
1 2 4136
11 9 19406
8 10 31700
4 3 14968
12 1 16644
12 9 26081
8 2 24725
9 11 19312
2 2 11872
8 2 16379
7 4 28965
8 9 4452
11 1 148
3 4 5477
11 12 2436
1 11 3711
2 4 2439
1 4 13848
2 8 19024
8 8 26398
9 11 31394
3 9 26325
1 1 17874
1 7 12688
2 3 19444
11 11 3975
12 1 27723
9 10 6671
1 2 16544
8 4 21463
12 6 17279
5 11 5885
9 5 13455
2 10 29201
3 2 13698
6 1 10595
6 7 8019
9 8 1078
11 4 707
5 7 26022
11 8 30809
12 9 32609
10 2 9046
12 1 16522
12 12 26706
9 1 3422
3 8 9092
9 12 23660
6 1 29666
5 2 7304
5 12 18328
2 2 21179
6 7 2954
5 10 16866
9 6 738
12 5 13752
6 3 11475
3 10 18809
10 10 3600
12 5 18030
2 10 187
2 3 4344
1 4 10414
7 4 6899
3 7 9060
6 11 2188
12 7 20986
9 11 12512
3 7 250
6 2 30202
6 2 1260
5 1 10253
8 4 29668
6 5 22013
12 7 17285
4 2 8593
4 4 4143
4 12 30693
7 2 32087
3 8 32505
5 6 18487
6 7 12140
3 1 7508
1 5 32198
8 5 22166
6 3 14555
2 7 19163
4 9 27436
12 1 6481
5 6 11101
12 6 10752
10 6 27657
12 11 19008
1 7 5538
10 12 10010
12 2 5412
5 5 16574
5 7 8376
4 6 6546
10 3 20391
9 2 10385
1 7 21797
4 4 18922
6 1 17885
3 1 23067
7 4 24136
11 4 9995
7 12 21551
1 4 16322
12 3 26609
3 5 14035
8 1 14940
10 7 29852
3 5 29246
6 6 3550
1 10 2295
4 2 2143
2 10 14263
1 12 23187
8 8 1830
6 8 5255
6 4 428
6 1 20338
8 4 3225
5 9 3783
4 3 1742
5 10 30876
7 4 3016
1 3 1205
1 3 12300
10 5 18595
9 11 18544
5 3 11441
12 6 24496
6 10 26771
8 12 30287
11 8 30742
9 8 5817
3 11 5952
5 12 15389
5 9 4771
5 3 5242
5 11 9169
3 6 22222
11 7 31531
3 2 19571
9 10 20364
4 7 22791
6 2 8571
10 4 20079
1 5 8932
5 5 17117
9 1 13708
12 8 31966
8 3 448
1 3 28116
2 7 5097
9 8 11636
5 2 2828
9 10 2326
8 12 31586
1 12 4097
6 6 3973
5 11 8691
7 11 30705
10 5 30611
2 4 11200
6 9 29849
7 1 12011
10 5 25033
6 10 20860
3 9 276
1 2 30827
3 11 22650
11 7 19497
9 3 8328
6 7 29179
12 11 2438
5 6 3256
3 7 5804
2 12 30340
12 8 12538
11 7 18596
6 8 23433
8 3 10104
1 10 12650
3 4 14400
6 8 6516
3 1 29501
7 7 30347
7 11 66
1 4 6984
9 8 17627
9 4 32271
9 4 4752
2 10 9960
7 1 18665
3 2 8901
11 3 4681
5 12 32756
12 11 29620
1 9 1520
2 12 1814
1 11 3786
5 8 13489
3 5 13030
12 9 27570
6 5 26560
4 10 805
5 4 22765
12 3 25528
1 10 11935
8 9 12306
9 8 14161
9 8 9387
8 2 4706
9 7 10596
12 10 6089
2 12 24139
3 6 23855
12 8 6747
2 2 29451
5 7 11797
4 11 21653
2 12 5435
5 7 7085
10 6 27163
9 12 26120
4 6 12850
7 10 2878
1 1 20230
12 2 23449
10 11 20361
9 3 11685
10 12 23912
2 3 5369
5 6 24334
7 11 18105
1 9 29254
1 7 176
1 5 27840
2 9 20000
9 5 26340
12 9 20889
3 4 19131
6 10 23916
6 5 17363
11 1 11424
6 9 3686
12 11 3186
10 3 21305
7 5 19135
9 4 19164
5 5 22509
6 1 7775
1 6 19254
5 12 13463
5 11 28244
5 6 8831
10 9 12809
7 2 6754
9 12 32504
9 7 18638
12 2 20159
1 8 24448
4 2 26465
7 8 28104
3 4 1880
4 1 25368
4 3 23273
1 11 955
3 5 17294
1 4 228
11 5 24728
4 12 7318
12 3 29776
4 10 5914
5 3 17218
11 2 26355
2 3 29563
4 4 15769
3 6 20446
5 6 27233
7 2 14299
9 4 6743
2 6 32297
11 6 3830
5 2 6497
3 11 32521
9 10 24443
10 3 15380
12 6 8612
1 8 15380
3 6 28649
6 10 6779
4 8 9373
12 11 21683
5 3 9627
8 3 17807
8 2 7582
11 1 105
3 3 23150
12 11 30698
11 8 3220
3 6 9641
12 1 27597
10 9 32549
10 12 20349
11 10 14788
12 3 11467
6 4 738
6 8 13355
3 5 12818
12 7 1669
5 7 27421
6 12 15930
6 1 29284
12 3 25270
10 4 29107
4 2 23887
8 2 25768
5 6 15515
10 1 11058
8 2 3986
7 8 9693
8 6 29705
8 4 4835
9 5 11373
9 4 29753
4 6 16076
5 9 26133
4 5 21381
11 5 19097
6 3 21569
6 2 23211
2 3 15353
8 7 21800
9 10 12086
2 10 31976
2 5 24537
12 9 11090
1 10 512
10 5 16505
10 7 16361
3 3 31467
7 2 14558
2 11 4291
5 3 15254
10 10 4251
8 10 9869
6 4 27758
5 2 14648
8 4 27021
9 5 14124
5 4 22577
10 1 6794
12 8 14935
1 6 17745
8 3 13535
3 4 14694
2 6 5931
5 7 28011
7 10 17586
11 2 26820
2 5 10558
11 9 31578
12 6 27606
4 2 13812
9 4 7544
3 10 20044
9 12 30776
11 9 26139
11 11 14429
6 8 20185
3 7 31888
3 8 27627
8 7 15163
8 7 21345
3 7 2732
3 11 20902
5 4 1685
8 1 3750
8 2 22782
5 6 21332
6 6 9678
9 7 25765
1 8 8040
5 12 9539
3 1 12313
4 8 16824
9 5 14151
9 9 8896
8 5 10912
8 5 20465
8 2 19133
10 5 24851
8 2 22514
9 4 9904
5 12 8002
4 5 25279
3 1 8370
8 5 20614
9 8 18285
10 12 26362
3 11 381
5 8 17229
6 4 18431
12 11 4458
1 8 10779
3 5 9864
12 1 31792
5 5 26146
1 7 14825
5 5 1015
6 7 17725
3 11 21980
8 8 17797
5 6 15998
8 5 20785
1 10 22135
7 6 4539
6 4 27447
3 8 1266
8 5 17330
10 2 12208
9 9 26837
3 5 21903
5 12 1066
7 8 26188
3 3 20795
9 5 7369
6 9 11921
5 5 5356
9 5 8541
4 5 13535
2 3 11056
10 9 31560
8 3 13141
10 2 26525
2 5 3487
11 11 4770
12 1 26312
9 3 31910
6 4 8898
5 2 25647
11 5 4987
7 1 29441
12 12 28422
4 9 2250
6 9 8752
5 7 12770
11 11 6365
1 1 15830
7 4 26566
3 2 15546
11 11 31606
2 5 15219
4 4 7824
9 7 13952
3 5 24001
1 6 14309
11 3 6645
5 3 16449
11 9 2466
10 9 17472
2 4 4168
5 6 32485
12 5 16244
10 7 28248
10 5 5865
3 4 21571
5 9 16832
2 3 21480
7 3 11420
10 12 5992
11 1 30014
4 1 4864
3 3 28200
3 10 22563
7 5 20748
11 5 17331
6 3 20787
12 6 31188
7 3 6957
9 2 26369
12 6 348
12 5 12661
3 11 11587
7 9 30466
9 12 15258
12 12 13032
5 3 15760
3 5 1108
12 8 17364
8 12 6531
3 10 26666
5 12 3270
4 7 20672
1 1 22489
3 10 29822
4 2 30532
11 10 2560
1 2 15050
4 11 4871
10 1 24837
12 3 29818
12 7 19404
12 7 3918
3 5 10227
7 5 26871
3 12 7803
1 7 12836
12 6 24154
11 1 28926
10 10 21855
4 11 20510
3 2 5077
11 8 9714
2 4 27132
11 1 16466
4 7 8052
12 1 28266
11 12 1055
2 10 14159
10 1 22321
2 1 13776
2 2 27750
9 11 16993
11 11 24724
9 6 31293
3 1 26129
4 6 24326
7 1 1701
11 10 19602
9 3 31751
3 4 27306
3 5 16658
7 5 7898
11 10 3371
12 2 26282
6 10 22689
8 12 31967
2 1 9185
2 1 19592
9 5 21719
11 7 2826
10 3 25818
7 6 28266
11 5 7912
6 12 26495
2 7 8487
4 2 8153
6 2 1506
9 9 18809
10 8 22396
11 7 8886
7 1 4117
9 12 31458
12 11 12484
2 4 5247
4 6 17860
7 9 2102
3 6 17382
11 2 22468
9 10 24850
6 4 17048
2 5 11477
8 7 13795
4 10 3878
5 4 28725
9 12 17117
12 2 13579
9 11 11936
7 12 18137
12 3 31276
9 11 24175
12 9 14144
12 12 3278
1 6 15519
11 5 28872
4 10 14036
7 3 31740
3 2 17870
5 5 15121
9 7 3938
9 2 17214
2 6 20057
8 9 7038
5 9 25238
1 3 16897
5 10 4723
9 5 24253
12 8 22126
9 4 23075
2 3 32688
11 1 31600
8 1 7971
4 2 29706
9 11 5643
8 12 26089
10 1 31321
4 6 4355
12 9 18490
7 8 30759
11 5 1930
7 1 2012
1 4 26421
6 6 10768
11 11 10671
8 2 18371
5 1 25860
1 3 5616
4 2 24113
4 12 15713
1 9 31432
11 2 1330
12 2 13582
6 10 13874
10 8 32268
12 9 349
2 6 22094
2 11 24103
5 2 29005
3 7 9553
3 10 16552
2 10 13182
11 6 7110
5 4 10946
9 3 11632
5 2 3295
5 1 13440

out:
3529