题目描述

有一个包含 $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$

输出格式

请输出答案。

样例 1

输入

3 3
1 2 5
2 3 6
1 3 12

输出

11

样例 2

输入

10 20
7 10 982219000
3 10 968366179
2 4 992330437
5 6 984414664
2 8 897295423
7 9 155604979
6 8 958833005
2 3 973209957
3 7 985173062
6 10 963895817
2 10 986243534
4 5 721724794
1 3 657562445
1 6 566370694
1 4 988050146
1 9 967817807
4 9 796531581
5 9 983960054
1 10 964450079
8 9 959369491

输出

952136560

样例 3

输入

10 20
5 6 871895994
8 10 873709822
3 5 454175869
6 10 980782191
2 6 901290987
1 8 298092290
4 8 693116157
4 5 947939338
7 8 934395075
7 9 759563833
5 8 779870031
4 6 919637355
2 9 822858749
4 10 855497285
3 7 954942051
1 2 950411658
4 7 665939990
3 4 634533617
5 7 908372507
1 9 591466693

输出

759563833

说明/提示

限制条件

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