AT_utpc2024_m Minimum Distance Tree

有一个 $N$ 个顶点 $M$ 条边的带权无向简单连通图 $G$，每个顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，权值为 $w_i$。 请判断，是否存在一个 $N$ 个顶点、顶点编号也为 $1$ 到 $N$ 的带权树 $T$，使得对于任意两个顶点 $u,v$，在图 $G$ 上 $u$ 到 $v$ 的最短路径长度等于树 $T$ 上 $u$ 到 $v$ 的最短路径长度。

输入通过标准输入给出，格式如下： > $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 以 $T$ 为一棵有 3 个顶点的树，边分别为顶点 $1,2$ 之间权值 $3$，顶点 $2,3$ 之间权值 $4$，即可满足条件。 ### 样例解释 2 不存在满足条件的 $T$。例如，如果 $T$ 是一棵有三条边，顶点 $1,2$ 之间边权为 $2$，顶点 $1,3$ 之间边权为 $2$ 的树，则在 $G$ 上 $1-2$ 的最短路距离为 $3$，而在该树上为 $2$，不相等，因此不满足要求。 ### 数据范围 - 所有输入均为整数。 - $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$ - 所给图是简单且连通的。 由 ChatGPT 5 翻译