#### 官方题解

```#include <bits/stdc++.h>
using namespace std;

const int maxn = 20, inf = 0x3f3f3f3f;
int n, m, d[maxn][maxn], dp[1<<17][maxn];

void floyd() {
for(int k = 1; k <= n; ++k)
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

void input() {
scanf("%d%d", &n, &m);
memset(d, inf, sizeof(d));
for(int i = 1; i <= n; ++i)
d[i][i] = 0;
for (int i = 0; i < m; ++i) {
int x, y, cost; scanf("%d%d%d", &x, &y, &cost);
if(cost < d[x][y]) d[x][y] = d[y][x] = cost;
}
}

int solve() {
memset(dp, inf, sizeof(dp));
dp[1][1] = 0;
for(int i = 1; i < (1<<n); ++i) {
for(int k = 1; k <= n; ++k) {
if(!(i&(1<<(k-1)))) continue;
for(int j = 1; j <= n; ++j) {
if(i&(1<<(j-1))) continue;
int to = i|(1<<(j-1));
dp[to][j] = min(dp[to][j], dp[i][k] + d[k][j]);
}
}
}
int res = inf;
for(int i = 2; i <= n; ++i)
res = min(res, dp[(1<<n)-1][i] + d[i][1]);
return res >= inf ? 0 : res;
}

int main() {
int T; scanf("%d", &T);
while(T--) {
input();
floyd();
printf("%d\n", solve());
}
return 0;
}
```