AT_arc165_c [ARC165C] Social Distance on Graph

有一个包含 $N$ 个顶点的简单连通无向图，顶点编号为 $1$ 到 $N$。图中有 $M$ 条带权无向边，第 $i$ 条边连接顶点 $A_i$ 和 $B_i$，权值为 $W_i$。对于连接两个顶点的简单路径，其权值定义为路径上所有边权的总和。 现在要对每个顶点染成红色或蓝色。请你求出满足以下条件的整数 $X$ 的最大值： - 对于任意两个染成相同颜色的不同顶点，它们之间的任意一条简单路径的权值都不少于 $X$。 简单路径的定义如下：对于图 $G$ 上的顶点 $X,Y$，顶点序列 $v_1,v_2,\ldots,v_k$，满足 $v_1=X$，$v_k=Y$，且对于 $1\leq i\leq k-1$，$v_i$ 和 $v_{i+1}$ 之间有边连接，这样的序列称为从 $X$ 到 $Y$ 的**步行**。如果 $v_1,v_2,\ldots,v_k$ 均互不相同，则称为从 $X$ 到 $Y$ 的**简单路径**（或简称**路径**）。

输入按以下格式从标准输入读入。 > $N$ $M$ > $A_1$ $B_1$ $W_1$ > $A_2$ $B_2$ $W_2$ > $\vdots$ > $A_M$ $B_M$ $W_M$

请输出答案。

### 限制条件 - $3 \leq N \leq 2 \times 10^5$ - $N-1 \leq M \leq \min\left(\frac{N(N-1)}{2}, 2 \times 10^5\right)$ - $1 \leq A_i < B_i \leq N$ - $1 \leq W_i \leq 10^9$ - 给定的图是简单连通无向图 - 输入的所有值均为整数 ### 样例解释 1 考虑 $X=11$ 时是否存在满足条件的染色方法。将顶点 $1,3$ 染为红色，顶点 $2$ 染为蓝色时，连接同色顶点的简单路径 $1-2-3$ 的权值为 $5+6=11$。这是所有同色顶点间简单路径权值的最小值，因此这种染色方法满足条件。当 $X\geq 12$ 时，不存在满足条件的染色方法。因此答案为 $11$。 由 ChatGPT 4.1 翻译