Before describing the specific problem, we first define that the graph $G = (V, E)$ discussed in this problem is an undirected weighted graph, where $V$ is the set of vertices and $E$ is the set of edges. The graph has no multiple edges and no self-loops. We use $w_G(u, v)$ to denote the weight of the edge $(u, v)$, and all $w_G(u, v)$ are positive integers.

For an undirected graph, we have the following basic concepts:

1. Path: For a graph $G = (V, E)$, a sequence of vertices $v_1, v_2, \dots, v_k$ is a path if for all $i \in [1, k)$, we have $(v_i, v_{i+1}) \in E$. $v_1$ is called the start vertex of the path, and $v_k$ is the end vertex.
2. Connected Graph: A graph $G = (V, E)$ is connected if for any $u, v \in V, u \neq v$, there exists a path from $u$ to $v$.
3. Multiple Edges and Self-loops: An undirected graph $G = (V, E)$ has multiple edges if there exist $u, v \in V$ such that the edge $(u, v)$ appears more than once in the graph. A self-loop is an edge of the form $(u, u)$.
4. Induced Subgraph: For a graph $G = (V, E)$ and a subset $C \subseteq V$, define the graph $G' = (C, E')$, where $(u, v) \in E'$ if and only if $u, v \in C$ and $(u, v) \in E$. $G'$ is called the induced subgraph of $C$ in $G$. We use $E_G(C)$ to denote the edge set $E'$ of the induced subgraph of $C$ in $G$. For edge weights, $w_{G'}(u, v) = w_G(u, v)$.

For a connected graph $G = (V, E)$, we have the following definitions:

1. $S(G)$: $S(G)$ is a subset of $E$ such that after removing all edges in $G$ with weights greater than $w_G(u, v)$ for $(u, v) \in S(G)$, the graph $G$ remains connected.
2. Partition: If $C_1, C_2, \dots, C_k$ are non-empty subsets of $V$ that are pairwise disjoint and their union is exactly $V$, and the induced subgraph of each $C_i$ ($1 \le i \le k$) is a connected graph, then $(C_1, C_2, \dots, C_k)$ is called a partition of graph $G$, and $k$ is called the degree of this partition.
3. $D(C_i, C_j)$: For two subsets $C_i, C_j$ of $V$, define $$D(C_i, C_j) = \min_{\substack{(u, v) \in E \\ u \in C_i, v \in C_j}} w_G(u, v)$$ If there exist no $u, v$ ($u \in C_i, v \in C_j$) such that $(u, v) \in E$, define $D(C_i, C_j) = \infty$.
4. $M(C)$: For a subset $C$ of $V$, let its induced subgraph be $G' = (C, E_G(C))$. If $G'$ is a connected graph, define $$M(C) = \min_{(u, v) \in E_G(C)} w_G(u, v)$$ If $|C| = 1$, define $M(C) = 0$. Here $|C|$ denotes the number of vertices in the vertex set $C$, and this notation is used consistently hereafter.
5. Semi-perfect: Given positive integers $Z[1], Z[2], \dots, Z[n]$, a partition $(C_1, C_2, \dots, C_k)$ of a connected graph $G$ is semi-perfect if for any $i, j$ ($1 \le i < j \le k$), we have $$D(C_i, C_j) > \min(M(C_i) + Z[|C_i|], M(C_j) + Z[|C_j|])$$
6. Perfect: A partition $(C_1, C_2, \dots, C_k)$ is perfect if it is semi-perfect, and additionally, for all $i \in [1, k]$, the graph $G_i = (C_i, E_G(C_i))$ has no semi-perfect partition of degree greater than 1.

Your task is to provide a perfect partition for the input connected graph $G$ and the values $Z[1], Z[2], \dots, Z[n]$.

Input

The first line contains two positive integers $n, m$, representing the number of vertices and the number of undirected edges in the input graph. The second line contains $n$ positive integers $Z[1], Z[2], \dots, Z[n]$ ($Z[i] \le 10^9$). The following $m$ lines each contain three positive integers $u, v, w$ ($1 \le u, v \le n, u \neq v, w \le 10^9$), representing an edge $(u, v)$ in the graph with weight $w$. The input undirected graph is guaranteed to have no multiple edges or self-loops.

Output

The output contains $k+1$ lines. The first line contains a positive integer $k$, representing the degree of the partition you provided. The following $k$ lines each describe a subset $C_i$. Each line starts with a positive integer $t$, representing $|C_i|$, followed by $t$ positive integers representing the vertex indices in $C_i$.

Examples

Input 1

5 8
3 3 2 2 1
1 2 3
1 3 5
1 4 6
2 4 10
2 5 5
4 5 8
3 6 15
5 6 7

Output 1

4
2 1 2
1 3
1 4
1 5

Input 2

See graph/graph.in and graph/graph.ans in the contestant directory.

Constraints

For 10% of the data, $n = 2$; For 30% of the data, $n \le 10$; For 60% of the data, $n \le 500, m \le 2,000$; For 100% of the data, $n \le 100,000, m \le 500,000$.