Minimum Network Upgrade Cost

You are given a network of n switches and m bidirectional links connecting them. Each switch can be upgraded to a core switch at a given cost. Upgrading a switch incurs an upgrade cost, and keeping a switch as non‐core incurs a transformation cost equal to the shortest distance from that switch to any core switch.

The total cost is defined as follows:

[ \text{Total Cost} = \sum_{v \in S} c_v + \sum_{u \notin S} d(u,S)]

where:

• S is the set of switches chosen to be upgraded (core switches), with \(1 \le |S| \le p\) (if no switch is upgraded, the cost is defined as \(\infty\)).
• \(c_v\) is the upgrade cost of switch \(v\).
• \(d(u,S)\) is the shortest distance from switch \(u\) to any upgraded switch \(v \in S\).

Your task is to choose up to \(p\) switches to upgrade such that the total cost is minimized.

The network topology is given by m bidirectional links, each with an associated weight.

inputFormat

The input is given as follows:

1. The first line contains three space-separated integers \(n\), \(m\), and \(p\) \( (1 \leq n \leq N,\ 1 \leq m \leq M,\ 1 \leq p \leq n)\), where \(n\) is the number of switches, \(m\) is the number of links, and \(p\) is the maximum number of switches that can be upgraded.
2. The second line contains \(n\) space-separated integers \(c_1, c_2, \dots, c_n\), where \(c_i\) is the cost to upgrade the \(i\)-th switch.
3. Each of the following \(m\) lines contains three space-separated integers \(u\), \(v\), and \(w\) representing a bidirectional link between switches \(u\) and \(v\) with weight \(w\).

Note: The switches are numbered from 1 to \(n\).

outputFormat

Output a single integer --- the minimum total cost to upgrade the network following the described strategy.

sample

3 3 2
5 10 3
1 2 1
2 3 1
1 3 2

6