#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int N = 1100;
const int mod = 998244353;
vector<int> v[N];
#define INF 0x3f3f3f3f
int n, m;
long long cnt;
int b[N];
int sum;
int st[N];
int a[N][N];//用的邻接矩阵 
int dist[N];
int prim()
{
	int ans = 0;
	memset(dist, 0x3f, sizeof dist);
	for (int i = 0; i < n; i++)
	{
		int t = -1;
		for (int j = 1; j <= n; j++)
		{
			if (!st[j] && (t == -1 || dist[t] > dist[j]))
			{
				t = j;
			}
		}
		//集合之外的距离最小的点 
		if (i!=0&& dist[t] == INF)//如果不是第一个点 
		{
			return INF;
		}
		if (i)
		{
			ans += dist[t];
		}
		st[t] = 1;//注意标记
		for (int j = 1; j <= n; j++)
		{
			dist[j] = min(dist[j], a[t][j]);//这里和djst不一样
		}
		//更新到集合的距离 
	}
	return ans;
}
void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i == j)
				a[i][j] = 0;
			else
				a[i][j] = INF;
		}
	}
	//初始化距离 
	for (int i = 1; i <= m; i++)
	{
		int l, r, w;
		cin >> l >> r >> w;
		a[l][r] = a[r][l] = min(a[l][r], w);//重边 
	}
	int x = prim();
	if (x == INF)
	{
		cout << "impossible";
	}
	else
		cout << x;
}
signed main()
{
	int t;
	t = 1;
	// cin>>t;
	while (t--)
	{
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
const int N = 4e5 + 10;
#define endl "\n"
typedef pair<int, int> pii;
int n;
int m;
int cnt;
int f[N];
struct node
{
    int l;
    int r;
    int v;
} a[N];
bool cmp(node p, node q)
{
    return p.v < q.v;
}
int find(int x)
{
    if (x != f[x])
    {
        f[x] = find(f[x]);
    }
    return f[x];
}
int b[N];
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
    }
    for (int i = 1; i <= n; i++)
    {
        f[i] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int x;
            cin >> x;
            if (i != j)
            {
                a[++cnt].l = i;
                a[cnt].r = j;
                a[cnt].v = x;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        a[++cnt].l = n + 1;
        a[cnt].r = i;
        a[cnt].v = b[i];
    }
    /*前者处理实际农场之间的连接费用，后者处理每个农场与虚拟井节点之间的开井费用，++cnt所以没有产生覆盖*/
    sort(a + 1, a + 1 + cnt, cmp);
    int sum = 0;
    int ans = 0;
    for (int i = 1; i <= cnt; i++)
    {
        int x = find(a[i].l);
        int y = find(a[i].r);
        if (x != y)
        {
            f[x] = y;
            ans += a[i].v;
        }
    }
    cout << ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    T = 1;
    // cin>>T;
    while (T--)
    {

        solve();
    }
    return 0;
}