class dsu:
    """Data structures and algorithms for disjoint set union problems.

    Given an undirected graph, it processes the following queries in O(alpha(n)) time (amortized).

    >   Edge addition

    >   Deciding whether given two vertices are in the same connected component

    Each connected component internally has a representative vertex.

    When two connected components are merged by edge addition, 
    one of the two representatives of these connected components becomes the representative of the new connected component.
    """

    __slots__ = ["n", "parent_or_size"]

    def __init__(self, n):
        """It creates an undirected graph with n vertices and 0 edges.

        Constraints
        -----------

        >   0 <= n <= 10 ** 8

        Complexity
        ----------

        >   O(n)
        """
        self.n = n
        self.parent_or_size = [-1] * n

    def merge(self, a, b):
        """It adds an edge (a, b).

        If the vertices a and b were in the same connected component, 
        it returns the representative of this connected component. 
        Otherwise, it returns the representative of the new connected component.

        Constraints
        -----------

        >   0 <= a < n 

        >   0 <= b < n

        Complexity
        ----------

        >   O(alpha(n)) amortized
        """
        # assert 0 <= a < self.n
        # assert 0 <= b < self.n
        x = self.leader(a)
        y = self.leader(b)
        if x == y:
            return x
        if self.parent_or_size[y] < self.parent_or_size[x]:
            x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        return x

    def same(self, a, b):
        """It returns whether the vertices a and b are in the same connected component.

        Constraints
        -----------

        >   0 <= a < n

        >   0 <= b < n

        Complexity
        ----------

        >   O(alpha(n)) amortized
        """
        # assert 0 <= a < self.n
        # assert 0 <= b < self.n
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        """It returns the representative of the connected component that contains the vertex a.

        Constraints
        -----------

        >   0 <= a < n

        Complexity
        ----------

        >   O(alpha(n)) amortized
        """
        # assert 0 <= a < self.n
        path = []
        while self.parent_or_size[a] >= 0:
            path.append(a)
            a = self.parent_or_size[a]
        for child in path:
            self.parent_or_size[child] = a
        return a

    def size(self, a):
        """It returns the size of the connected component that contains the vertex a.

        Constraints
        -----------

        >   0 <= a < n

        Complexity
        ----------

        >   O(alpha(n)) amortized
        """
        # assert 0 <= a < self.n
        return -self.parent_or_size[self.leader(a)]

    def groups(self):
        """It divides the graph into connected components and returns the list of them.

        More precisely, it returns the list of the "list of the vertices in a connected component". 
        Both of the orders of the connected components and the vertices are undefined.

        Complexity
        ----------

        >   O(n)
        """
        result = [[] for _ in range(self.n)]
        for i in range(self.n):
            result[self.leader(i)].append(i)
        return [g for g in result if g]


N, M, K = map(int, input().split())
As = list(map(int, input().split()))
XYZs = [tuple(map(int, input().split())) for _ in range(M)]

INF = 10 ** 18

adj = [[INF] * N for _ in range(N)]
for X, Y, Z in XYZs:
    X -= 1; Y -= 1
    adj[X][Y] = adj[Y][X] = min(adj[X][Y], Z)

for k in range(N):
    for i in range(N):
        for j in range(N):
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])

def calc(indices):
    t = []
    for idx_i, i in enumerate(indices):
        for idx_j, j in enumerate(indices):
            if idx_i == idx_j:
                continue
            t.append((adj[i][j], idx_i, idx_j))
    t.sort(key=lambda t: t[0])
    uf = dsu(K)
    ret = 0
    for c, i, j in t:
        if not uf.same(i, j):
            uf.merge(i, j)
            ret += c
    return ret 


def popcnt(n):
    "https://atcoder.jp/contests/abc152/submissions/9619555"
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c


answer = INF
for s in range(1 << N):
    if popcnt(s) != K:
        continue
    indices = []
    tmp = 0
    for i in range(N):
        if s & (1 << i):
            indices.append(i)
            tmp += As[i]
    tmp += calc(indices)
    answer = min(answer, tmp)

print(answer)