配点 : 100 点
問題文
在顶部 编号为 1 减去 N 有 N 頂点 M 由边组成的加权简单连通无向图 G 。 i 第一条边是顶点 u_i,v_i 所连接的边的权重为 w_i 。
在顶部 编号为 1 减去 N 有 N 加权树的顶点 T ,请判断是否存在使任意 2 頂点 u,v , 您可以获得 G 以上 u-v 的最短路径长度等于 T 以上 u-v 的最短路径长度的情况。
制約
- 所有输入均为整数
- 2 \leq N \leq 5 \times 10^5
- N-1 \leq M \leq 5 \times 10^5
- 1 \leq u_i, v_i \leq N
- 1 \leq w_i \leq 10^9
- 给定的图很简单且连通
入力
输入是按以下格式从标准输入给出的。
N M u_1 v_1 w_1 u_2 v_2 w_2 \vdots u_M v_M w_M
出力
作为上述的 T 存在则 Yes 如果不存在。
步行 No 。
入力例 1
3 3 1 2 3 2 3 4 3 1 100
出力例 1
Yes
T ,顶点之间存在权重为 1,2 的边,顶点 3 的边数为 2,3 的边,顶点 4 。 3 顶点的树满足条件。
入力例 2
3 3 1 2 3 2 3 4 3 1 2
出力例 2
No
满足条件 T 不存在。例如,顶点 1,2 的边,顶点 2 的边数为 1,3 的边,顶点 2 。 3 的树,是在G 上的 1-2 的最短路径长度等于 3 ,而在这棵树上的 1-2 的最短路径长度等于 2 并不相同,因此不满足条件。