#1013. I 人的社交需要距离

I 人的社交真的很需要距离。为了方便称呼这位 I 的友人，我们不妨叫他小I。

为了描述这个小I的社交网络，我们用一个连通无向图来表示。每个人都是这张图上的一个节点，每一个社交关系都是两个点之间的边。具体的，这个图有 个节点，标号从 到 。这张图有 张有权值的边，第 条边连接 和 ，权值为 。我们定义连接图上两个点的简单路径的权值为简单路径上每一条边的权值和。

你的任务是帮助小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

样例解释 1

考虑是否存在一种着色方案满足 的条件。如果我们将顶点 和 涂成红色，顶点 涂成蓝色，那么连接相同颜色顶点的简单路径 的权重为 。这是连接相同颜色顶点的简单路径的最小权重，因此这种着色方案满足条件。

可以证明，对于 或更高的情况，不存在满足条件的着色方案。因此，答案是 。

数据范围

对于所有的数据，满足：