Problem Description

Shiomushi-kun is solving the following problem:

The Kingdom of Paken consists of $ N $ cities $1,\ 2,\ \ldots,\ N$ and $ M $ roads $1,\ 2,\ \ldots,\ M$. You are given sequences $ A, B, C $ of length $ M $ representing the road information, where road $ i $ connects city $ A_i $ and city $ B_i $ bidirectionally with a cost of $ C_i $ to traverse.

The Kingdom of Paken is hosting an event over $ N $ days in conjunction with the 6th Technical Room Programming Contest. On the $ i $th day, an event is held in city $ i $, so you need to go to city $ i $. For each $i\ =\ 1,\ 2,\ \ldots,\ N$, find the minimum total cost to travel from city $ 1 $ to city $ i $ and then to city $ N $. Note that you can visit the same city or road multiple times, including cities $ 1 $ and $ N $.

Shiomushi-kun finds this problem easy. He has determined that the answer for the $ i $th day is $ D_i $ for each $i\ =\ 1,\ 2,\ \ldots,\ N$.

However, Shiomushi-kun has a gap in his memory and forgot what $ A, B, C $ were. Please find one possible $ A, B, C $ for him, or report that such a set does not exist.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ D_1 $ $ D_2 $ $\ldots$ $ D_N $

Output Format

If no $ A, B, C $ satisfies the conditions, output No. If it exists, output in the following format:

Yes $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $\vdots$ $ A_M $ $ B_M $ $ C_M $

This must satisfy the following constraints:

• $1\ \leq\ A_i\ <\ B_i\ \leq\ N$ $(1\ \leq\ i\ \leq\ M)$
• $0\ \leq\ C_i\ \leq\ 10^9$ $(1\ \leq\ i\ \leq\ M)$
• $(A_i,\ B_i)\ \neq\ (A_j,\ B_j)$ $(1\ \leq\ i\ <\ j\ \leq\ M)$
• It is possible to travel from any city to any other city using zero or more roads.
• When solving the original problem, the answer for the $ i $th day is $ D_i $.
• Each $ C_i $ $(1\ \leq\ i\ \leq\ M)$ is an integer.

If multiple $ A, B, C $ satisfy the conditions, any one of them can be output.

Sample Input and Output

Sample Input #1

5 7
5 5 6 6 5

Sample Output #1

Yes
1 2 1
1 3 2
1 4 6
2 4 5
2 5 4
3 4 3
4 5 1

Sample Input #2

5 4
10 10 10 10 10

Sample Output #2

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

Sample Input #3

3 100
1 3 2

Sample Output #3

No

Notes/Hints

Constraints

• $1\ \leq\ N,M\ \leq\ 10^5$
• $0\ \leq\ D_i\ \leq\ 10^9$ $(1\ \leq\ i\ \leq\ N)$
• All inputs are integers

Sample Explanation 1

In this output example, for instance, the minimum cost path on the 3rd day involves traversing roads $ 2, 6, 7 $ in sequence. The costs for traversing these roads are $ 2, 3, 1 $ respectively, totaling $ 6 $.

Sample Explanation 3

No $ A, B, C $ satisfies the conditions. Original idea: shiomusubi496

见题面 Input 部分

见题面 Output 部分