图上的社交距离

时间限制：5s
空间限制：512MB

题目描述

有一张含 $N$ 个顶点、$M$ 条边的简单连通无向图，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $A_i,B_i$，权值为 $W_i$。一条简单路径的权值定义为路径上所有边权之和。

你要把每个顶点染成红色或蓝色。求最大的整数 $X$，使得存在一种染色方案，满足任意两个颜色相同的不同顶点之间的每一条简单路径的权值都不少于 $X$。

简单路径是指经过的顶点互不相同的路径。

输入格式

第一行输入两个整数 $N,M$。

接下来 $M$ 行，每行输入三个整数 $A_i,B_i,W_i$，表示一条无向边。

输出格式

输出答案。

样例输入 1

3 3
1 2 5
2 3 6
1 3 12

样例输出 1

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

样例输出 2

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

样例输出 3

759563833

数据范围

对于所有数据，$3\le N\le 2\times 10^5$，$N-1\le M\le\min\left(\frac{N(N-1)}2,2\times10^5\right)$，$1\le A_i<B_i\le N$，$1\le W_i\le10^9$。保证图简单且连通。