#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = ((b) - 1); i >= (int)(a); --i)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) ((int)x.size())

constexpr int INF = 1001001001001001001LL;

using pii = pair<int, int>;
using Mat = vector<vector<int>>;

struct UnionFind {
    vector<int> data;
    UnionFind(int n) : data(n, -1) {}
    void unite(int a, int b) {
        a = root(a);
        b = root(b);
        if (a == b) return;
        if (size(a) > size(b)) swap(a, b);
        data[b] += data[a];
        data[a] = b;
    }
    int root(int x) {
        return (data[x] < 0 ? x : (data[x] = root(data[x])));
    }
    int size(int x) { 
        return -data[root(x)];
    }
    bool same(int a, int b) {
        return root(a) == root(b);
    }
};

// [from, to)
bool check_connected(Mat &adj, int from, int to) {
    int N = adj.size();
    UnionFind uf(N);
    rep(i, 0, N) {
        rep(j, 0, N) {
            if (i == j) continue;
            if (adj[i][j] > 0) {
                uf.unite(i, j);
            }
        }
    }
    set<int> s;
    rep(i, from, to) {
        s.insert(uf.root(i));
    }
    return sz(s) == 1;
}

int &get_cost(Mat &adj, int i, int j) {
    if (i > j) swap(i, j);
    return adj[i][j];
}

bool solve() {
    int N, M;
    cin >> N >> M;
    if (N == 0 && M == 0) return false;

    vector<pii> H(N);
    rep(i, 0, N) {
        cin >> H[i].first;
        H[i].second = i;
    }
    sort(all(H));
    vector<int> ord(N), T(N);
    rep(i, 0, N) {
        ord[H[i].second] = i;
        T[i] = H[i].first;
    }

    Mat ADJ(N, vector<int>(N, -1));
    rep(i, 0, M) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        a = ord[a];
        b = ord[b];
        get_cost(ADJ, a, b) = c;
    }

    int X = N - 1;
    {
        auto adj = ADJ;
        if (!check_connected(adj, 0, N)) {
            cout << "0" << endl;
            return true;
        }
        rep(i, 0, N) {
            rep(j, 0, N) {
                if (get_cost(adj, i, j) > 0) {
                    get_cost(adj, i, j) = -1;
                }
            }
            if (i + 1 < N && T[i] == T[i + 1]) continue;

            if (!check_connected(adj, i + 1, N)) {
                X = i;
                break;
            }
        }
        while (X > 0 && T[X - 1] == T[X]) X--;
    }

    UnionFind uf(N);
    int ans = 0;
    // X~N番の頂点からなる部分グラフのMSTのコストを加算
    {
        vector<tuple<int, int, int>> edge;
        edge.reserve(N * N);
        rep(i, X, N) {
            rep(j, X, N) {
                if (get_cost(ADJ, i, j) > 0) {
                    edge.push_back(make_tuple(get_cost(ADJ, i, j), i, j));
                }
            }
        }
        sort(all(edge));
        
        rep(i, 0, sz(edge)) {
            int c, a, b;
            tie(c, a, b) = edge[i];
            if (uf.same(a, b)) {
                continue;
            }
            uf.unite(a, b);
            ans += c;
        }
    }

    // 0 ~ X-1番の頂点について、辺を張る(コストを加算)
    {
        vector<tuple<int, int, int>> edge;
        rrep(i, 0, X) {
            rep(j, i + 1, N) {
                if (get_cost(ADJ, i, j) > 0) {
                    edge.push_back(make_tuple(get_cost(ADJ, i, j), i, j));
                }
            }
            if (i > 0 && T[i - 1] == T[i]) {
                continue;
            }
            sort(all(edge));
            rep(i, 0, sz(edge)) {
                int c, a, b;
                tie(c, a, b) = edge[i];
                if (uf.same(a, b)) {
                    continue;
                }
                uf.unite(a, b);
                ans += c;
            }
            edge.clear();
        }
    }

    cout << ans << endl;
    return true;
}

signed main() {
    while (1) {
        if (!solve()) break;
    }
}


Measured memory_bytes: 4444