Rail Network Reduction

Byteland Railways has decided to reduce its rail network as much as possible while ensuring connectivity between the stations that will be retained. You are given a description of the rail network, consisting of stations and bidirectional rail segments with associated maintenance costs, as well as the list of stations that will not be removed. Although remaining rail segments (the ones you choose to keep) may run through stations that are going to be removed, it is required that for every pair of stations that are not removed there exists a path using the remaining segments. Moreover, the total maintenance cost of the selected segments should be at most twice the minimum possible cost that guarantees this connectivity. A minimum spanning tree (MST) of the entire network always satisfies these conditions, since it connects all stations with minimum cost.

Your task is to determine a set of rail segments (by choosing an MST on the whole network) and output the total maintenance cost along with the list of segments that should remain.

Note: The maintenance cost of each segment is a positive integer. There is at most one segment connecting any pair of stations, and the network is initially connected.

In mathematical terms, if the MST has total cost \(C_{MST}\), then the chosen set’s cost \(C\) satisfies \(C \leq 2 \times C_{MST}\). Since the MST is optimal, it is a valid solution.

inputFormat

The first line of the input contains three integers \(n\), \(m\) and \(k\) where \(n\) is the number of stations, \(m\) is the number of rail segments, and \(k\) is the number of stations that will not be removed.

The second line contains \(k\) distinct integers denoting the IDs of the stations that will remain. Stations are numbered from 1 to \(n\).

The following \(m\) lines each contain three integers \(u\), \(v\) and \(w\), representing a bidirectional rail segment between stations \(u\) and \(v\) with a maintenance cost \(w\) (a positive integer).

outputFormat

First, output the total cost of the maintenance for the selected rail segments on one line.

Then, output each of the selected rail segments on a separate line in the format:

u v w

where \(u\) and \(v\) are the station IDs connected by the segment and \(w\) is the maintenance cost for that segment. The order of the segments does not matter.

sample

4 5 3
1 2 3
1 2 1
2 3 2
3 4 3
4 1 4
2 4 1

4
1 2 1
2 4 1
2 3 2