Mystical Trees Network

You are given N mystical trees, each with an associated power level, and M bidirectional pathways connecting pairs of trees. Each pathway has a cost associated with it. Your task is to determine the minimum cost required to connect all the mystical trees so that every tree can be reached from any other tree. If it is impossible to connect all trees (i.e. the graph is disconnected), output -1.

Note: The power levels of the trees do not affect the connection cost. They are provided for thematic purposes.

The problem can be modeled as finding a Minimum Spanning Tree (MST) of a graph. Recall the MST problem can be solved using greedy algorithms such as Kruskal's or Prim's algorithm. In mathematical terms, if we denote the set of edges in the MST by \(E'\), then the answer is:

\(\text{Total Cost} = \sum_{e \in E'} cost(e)\)

and if \(|E'| \neq N-1\) (i.e. the graph is not connected), then output -1.

inputFormat

The first line contains two integers N and M separated by space, where N is the number of mystical trees and M is the number of pathways.

The second line contains N integers representing the power levels of the trees.

The next M lines each contain three integers u, v, and cost representing a pathway between tree u and tree v with the given cost.

outputFormat

Output a single integer which is the minimum cost to connect all mystical trees. If it is impossible to connect all trees, output -1.

## sample

4 5
10 20 30 40
1 2 5
1 3 10
2 3 6
2 4 8
3 4 3

14