import java.util.*

class UnionFind(val size: Int){
    private val array = IntArray(size){-1}
    fun find(a: Int): Int {
        if (array[a] < 0) return a
        array[a] = find(array[a])
        return array[a]
    }
    fun isSame(a: Int, b: Int): Boolean {
        return find(a) == find(b)
    }
    fun merge(a: Int, b: Int): Unit {
        val ar = find(a)
        val br = find(b)
        if (ar != br) {
            if (array[ar] < array[br]){
                array[ar] += array[br]
                array[br] = ar
            }else{
                array[br] += array[ar]
                array[ar] = br
            }
        }
    }
}
class PersistentUnionFind(val size: Int) {
    private val parentOrSize = IntArray(size){-1}
    private val mergeTime = IntArray(size){Int.MIN_VALUE}
    fun parentAt(a: Int, time: Int): Int {
        var current = a
        while(mergeTime[current] >= -time) {
            current = parentOrSize[current]
        }
        return current
    }
    fun timeWhenMerged(a: Int, b: Int): Int? {
        var ca = a
        var cb = b
        var lastTime = 0
        while(ca != cb && (parentOrSize[ca] >= 0 || parentOrSize[cb] >= 0)) {
            if (mergeTime[ca] > mergeTime[cb]) {
                lastTime = mergeTime[ca]
                ca = parentOrSize[ca]
            }else {
                lastTime = mergeTime[cb]
                cb = parentOrSize[cb]
            }
        }
        return if (ca != cb) null else -lastTime
    }
    fun currentParent(a: Int): Int {
        return if (parentOrSize[a] < 0) a
        else currentParent(parentOrSize[a])
    }
    fun mergeAt(a: Int, b: Int, time: Int): Unit {
        val ar = currentParent(a)
        val br = currentParent(b)
        if (ar != br) {
            if (parentOrSize[ar] < parentOrSize[br]) {
                parentOrSize[ar] += parentOrSize[br]
                parentOrSize[br] = ar
                mergeTime[br] = -time
            }else {
                parentOrSize[br] += parentOrSize[ar]
                parentOrSize[ar] = br
                mergeTime[ar] = -time
            }
        }
    }
}
data class Bridge(val from: Int, val to: Int, val cost: Int)
fun main(args: Array<String>?): Unit{
    problem@ while(true){
        val (n, m) = readLine()!!.trim().split(' ').map(String::toInt)
        if (n == 0 && m == 0) return
        val islands = IntArray(n){readLine()!!.trim().toInt()}
        val bridges = List(m){
            val (a, b, c) = readLine()!!.trim().split(' ').map(String::toInt)
            Bridge(a - 1, b - 1, c)
        }.sortedByDescending{Math.min(islands[it.from], islands[it.to])}
        val persistentUnionFind = PersistentUnionFind(n)
        val lastIsland = islands.indices.maxBy(islands::get)!!
        for ((a, b, _) in bridges) {
            persistentUnionFind.mergeAt(a, b, islands[lastIsland] - Math.min(islands[a], islands[b]))
        }
        var lastTime = islands[lastIsland]
        for (i in 1 until n) {
            val mergeTime = persistentUnionFind.timeWhenMerged(lastIsland, (lastIsland + i) % n)
            if (mergeTime == null) {
                println(0)
                continue@problem
            }
            if (mergeTime > islands[lastIsland] - islands[(lastIsland + i) % n] && lastTime > islands[lastIsland] - mergeTime) {
                lastTime = islands[lastIsland] - mergeTime
            }
        }
        val union = UnionFind(n)
        var cost = 0
        val (after, before) = bridges.partition { b -> Math.min(islands[b.from], islands[b.to]) >= lastTime  }
        for ((a, b, c) in after.sortedBy(Bridge::cost)) {
            if (!union.isSame(a, b)) {
                union.merge(a, b)
                cost += c
                //println("${a + 1} ${b + 1} $c")
            }
        }
        val queue = PriorityQueue<Bridge>(compareBy(Bridge::cost))
        var current = 0
        while(current < before.size) {
            queue.add(before[current])
            while(current + 1 < before.size && Math.min(islands[before[current].from], islands[before[current].to]) == Math.min(islands[before[current + 1].from], islands[before[current + 1].to])) {
                queue.add(before[++current])
            }
            while(queue.isNotEmpty()) {
                val (a, b, c) = queue.poll()
                if (!union.isSame(a, b)) {
                    union.merge(a, b)
                    cost += c
                    //println("${a + 1} ${b + 1} $c")
                }
            }
            ++current
        }
        println(cost)
    }
}


Measured memory_bytes: 114292