#include <bits/stdc++.h>
using namespace std;
void read(int &x){
	char ch=getchar();x=0;
	for (;ch==' '||ch=='\n';ch=getchar());
	for (;ch!=' '&&ch!='\n';x=x*10+ch-'0',ch=getchar());
}
void write(int x){
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
int n,m,ans=2e9,SUM,dis[17][17],num[33000],dp[33000][17];
int main(){
	read(n),read(m);
	for (int i=0;i<m;i++){
		int x,y,c;read(x),read(y),read(c);SUM+=c;
		dis[x-1][y-1]=dis[y-1][x-1]=c;
	}
	for (int i=1;i<(1<<n);i++){
		int cnt;
		for (int j=0;j<n;j++) if ((1<<j)&i){
			cnt=j;break;
		}
		num[i]=num[i^(1<<cnt)];
		for (int k=0;k<n;k++) if ((1<<k)&i) num[i]+=dis[k][cnt];
	}
	for (int i=0;i<33000;i++) for (int j=0;j<17;j++)dp[i][j]=-5e8;
	dp[1][0]=0;
	for (int i=1;i<(1<<n);i++){
		for (int j=0;j<n;j++){
			for (int k=0;k<n;k++) if ((i&(1<<j))>0 && (i&(1<<k))>0 && dis[j][k]) dp[i][j]=max(dp[i][j],dp[i^(1<<j)][k]+dis[j][k]);
			for (int k=i;k>=0;k=(k-1)&i){
				if (k&(1<<j)) dp[i][j]=max(dp[i][j],dp[i^k|(1<<j)][j]+num[k]);
				if (k==0) break;
			}
		}
		if ((1<<(n-1))&i) ans=min(ans,SUM-dp[i][n-1]);
	}
	write(ans);
}
#include <bits/stdc++.h>

using namespace std;

#define FOR(i,s,e) for((i)=(s);(i)<(int)(e);(i)++)
#define REP(i,e) FOR(i,0,e)

#define all(o) (o).begin(), (o).end()
#define psb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))

typedef long long ll;
typedef pair<int, int> PII;

const double EPS = 1e-10;

const int INF = 1000 * 1000 * 1000;
const int N = 100;
int n;
int c[N][N];
int d[N];
bool used[N];

int prim() {
  int i, res = 0;
  for (i=0; i<n; i++) {
    d[i] = INF;
    used[i] = false;
  }

  d[0] = 0;
  while (1) {
    int v = -1;
    for (i=0; i<n; i++)
      if (!used[i] && (v==-1 || (v>=0 && d[i]<d[v])))
        v = i;
  
    if (v==-1) break;
    used[v] = true;
    res += d[v];
    for (i=0; i<n; i++)
      d[i] = min(d[i], c[v][i]);
  }

  return res;
}

int main() {
  int i, j;
  scanf("%d ", &n);
  for (i=0; i<n; i++)
    for (j=0; j<n; j++) {
      scanf("%d ", &(c[i][j]));
      if (c[i][j]==-1) c[i][j] = INF;
    }
  printf("%d\n", prim());
  return 0;
}