← 返回题目列表

AtCoder · tkppc6_2_f

F. 最短路径构建

中文机器翻译题面 查看原题

配点 : 600 点

問題文

Shiomusubi 正在解决以下问题。 它由

帕肯王国是 N 镇 1, 2, \ldots, N 和 按字典顺序比较 M 书籍之路 1, 2, \ldots, M 组成。 代表道路信息的长度 M 序列 使用 A,B,C 已给出,道路 双向连接 i 是街道 A_i 和城市 B_i 即可通过。 C_i 。

在帕肯王国,结合技术室后台编程大赛#6, N 活动将持续几天。 i 当天所在城市 活动将在 i 举行,所以 您需要转到 i 。 i = 1, 2, \ldots, N , 当我输入 i 当天所在城市 1 从城市出发 转至 i 穿越城市 求前往 N 的最低总成本。 然而,顶点 假设多次经过同一个顶点或同一条道路是可以的,包括 1,N 。

如果你问 Shiomusubi,这个问题很简单。 盐结君是 i = 1, 2, \ldots, N 对于每个, 第 i 今天的答案是 D_i 。

然而,盐结君在某些方面有所欠缺,所以 我忘了 A, B, C 是什么。 为了你,盐结 什么可以被视为 A, B, C 什么可以被认为是 1 请帮我找一个。

但是,如果不存在,请报告。 如果

制約

  • 1 \leq N,M \leq 10^5
  • 0 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
D_1 D_2 \ldots D_N

出力

满足条件 A, B, C 不存在,一行 输出 No 。如果存在,则按照以下格式输出。

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

但是,这必须满足以下约束。

  • 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)
  • 从任何城市到任何城市 0 可以使用多条道路行驶
  • 当你解决原来的问题时, i 今天的答案是 D_i 变为
  • 各 i\ (1 \leq i \leq M) 中, 输出C_i 是一个整数(在 14:51 添加)

此外,如果满足条件 A, B, C ,则可以输出其中任何一个。 包含


入力例 1

5 7
5 5 6 6 5

出力例 1

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

在这个输出例中,例如 3 在第几天移动的成本最小的路线是依次经过道路的路线。 2, 6, 7 移动道路所需的成本分别是 2, 3, 1 所以总共是 6 。


入力例 2

5 4
10 10 10 10 10

出力例 2

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

入力例 3

3 100
1 3 2

出力例 3

No

满足条件 A, B, C 不存在。

原案: shiomusubi496