class UnionFind
	def initialize
		@obj_to_node = {}
	end

	def add(obj)
		@obj_to_node[obj] ||= Node.new(obj)
	end

	def size(x = nil)
		x ? @obj_to_node[x].root.size : @obj_to_node.size
	end

	class Node
		def initialize(obj)
			@obj = obj
			@parent = self
			@size = 1
			@rank = 0
		end

		def root
			return self if @parent == self
			@parent = @parent.root
		end	

		attr_accessor :parent, :size, :rank
	end

	def union(x, y)
		u = (@obj_to_node[x] ||= Node.new(x)).root
		v = (@obj_to_node[y] ||= Node.new(y)).root
		return if u == v
		if u.rank > v.rank
			v.parent = u
			u.size += v.size
		elsif v.rank > u.rank
			u.parent = v
			v.size += u.size
		else
			u.parent = v
			v.rank += 1
			v.size += u.size
		end
	end

	def same?(x, y)
		return false unless u = @obj_to_node[x]
		return false unless v = @obj_to_node[y]
		u.root == v.root
	end
end

loop {
	n, m = gets.split.map &:to_i
	break if n == 0
	
	nodes = [nil] + (1..n).map{|i| [i, gets.to_i]}

	available = {}
	(1..m).each{
		i, j, c = gets.split.map &:to_i
		u = nodes[i]
		v = nodes[j]
		r = (u[1] < v[1] ? u : v)
		available[r] ||= []
		available[r] << [u, v, c]
	}

	nodes.shift
	nodes.sort_by!(&:last)

	tree_size = 0
	node_num = 0
	uf = UnionFind.new
	separator = Float::INFINITY
	disconnected = false

	i = nodes.size-1
	until i < 0 
		max = nodes[i][1]
		while i >= 0 && nodes[i][1] == max
			v = nodes[i]
			node_num += 1
			edges = (available[v] || [])
			
			edges.sort_by!(&:last)
			edges.each{|u, v, c|
				if !uf.same?(u, v)	
					uf.union(u, v)
					tree_size += 1
				end
			}
			i -= 1
		end

		if tree_size == node_num - 1
			if disconnected
				separator = v[1]
			end
			disconnected = false
		else
			disconnected = true	
		end
	end	
	edges = []

	sum = 0
	tree_size = 0
	node_num = 0
	uf = UnionFind.new

	until nodes.empty? || nodes[-1][1] <= separator 
		v = nodes.pop
		node_num += 1
		edges += (available[v] || [])
	end

	until nodes.empty?
		max = nodes[-1][1]
		while !nodes.empty? && nodes[-1][1] == max
			v = nodes.pop
			node_num += 1
			edges += (available[v] || [])
		end
			
		edges.sort_by!(&:last)
		edges.each{|u, v, c|
			if !uf.same?(u, v)	
				uf.union(u, v)
				sum += c
				tree_size += 1
			end
		}
		edges = []
	end
	p tree_size == n - 1 ? sum : 0
}