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

int f[25010];
int A , B;

struct node{int start , end , w;}c[25010];

void init(int n) {for (int i = 0; i < n; i++) f[i] = i;}

int fjjh(int x) {return f[x] == x ? x : fjjh(f[x]);}

void merge(int a , int b) {f[fjjh(b)] = fjjh(a);}

bool cmp(node a , node b) {return a.w < b.w;}

int main() {
	cin >> A >> B;
	int graph[B][B];
	for (int i = 0; i < B; i++) for (int j = 0; j < B; j++) {cin >> graph[i][j]; if (graph[i][j] == 0 && i != j) graph[i][j] = A;}
	
	int m = 0;
	for (int i = 0; i < B; i++) {
		for (int j = 0; j < B; j++) {
			if (j != i) {
				c[m].start = i;
				c[m].end = j;
				c[m].w = graph[i][j];
				m++;
			}
		}
	}
	
	sort(c , c + m , cmp);
	init(m);
	
	if (B == 1) cout << A;
	else {
		int k = 0 , sum = A , flag = 0;
			for (int i = 0; i < m; i++) {
				if (fjjh(c[i].start) != fjjh(c[i].end)) {
				sum += c[i].w;
				merge(c[i].start , c[i].end);
				k++;
				if (k == B - 1) {flag = 1; cout << sum; break;}
			}
		} 
	}
	
	return 0;
}