We ran out of ideas, so here's a template single source shortest path problem.

Given a graph with ~N~ nodes and ~M~ directed edges, where the ~i^{th}~ edge goes from node ~u_i~ to ~v_i~ with weight ~w_i~, compute the minimum cost to reach each node starting from node ~1~. It is guaranteed that all nodes are reachable from node ~1~.

Constraints

~1 \le N \le 2 \times 10^5~
~0 \le M \le 2 \times 10^5~

~1 \le u_i, v_i \le N~
~1 \le w_i \le 10^9~

It is guaranteed that all nodes are reachable from node ~1~.

Output Specification

The first line contains two space-separated integers, ~N~ and ~M~, the number of nodes and the number of directed edges in the graph.

The next ~M~ lines each contain three space-separated integers, the ~i^{th}~ line containing ~u_i~, ~v_i~, and ~w_i~, indicating that there is an edge from node ~u_i~ to ~v_i~ with weight ~w_i~.

Input Specification

The first line contains ~N~ space-separated integers, where the ~i^{th}~ integer is the minimum cost to reach node ~i~ starting from node ~1~.

Sample Output

6 6
1 2 4
1 3 7
2 3 2
2 4 5
3 6 1
6 5 2

Sample Input

0 4 6 9 7 8