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 翻译