#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;

const int N = 505;
int dad[N];
int ans = 0;
int val[N][N];
int a, b; //价格  物品数量

struct bri
{
    int a;
    int b;
    int v;

    bool operator<(bri b1) const
    {
        return v < b1.v;
    }
} br[N];

inline void init()
{
    for (int i = 1; i < b + 1; i++)
        dad[i] = i;
}

inline int find(int x)
{
    return x == dad[x] ? x : (dad[x] = find(dad[x]));
}

int main()
{
    int s = 0;
    cin >> a >> b;

    for (int i = 1; i < b + 1; i++)
        for (int j = 1; j < b + 1; j++)
            cin >> val[i][j];

    for (int i = 1; i < b + 1; i++)
        for (int j = i + 1; j < b + 1; j++)
        {
            br[++s].a = i;
            br[s].b = j;
            if (!val[i][j] || val[i][j] > a)
                br[s].v = a;
            else
                br[s].v = val[i][j];
        }

    init();

    sort(br + 1, br + 1 + s);
    // for (int i = 1; i < s + 1; i++)
    //     cout << br[i].a << ' ' << br[i].b << ' ' << br[i].v << endl;
    for (int i = 1; i < s + 1; i++)
    {
        int aa = find(br[i].a), bb = find(br[i].b);

        if (aa != bb)
        {
            dad[aa] = bb;
            b--;
            ans += br[i].v;
        }

        if (b == 1)
        {
            cout << ans + a;
            return 0;
        }
    }

    cout << ans + a;
}