#p4920. [ABC317C] Remembering the Days

[ABC317C] Remembering the Days

题面翻译

一个有 MM 粒子边的 NN 粒子。

第 i 个 MM 粒子的长度为 CiC_i。

图中最长简单路径的长度。

题目描述。

在一个地区有 N N 个城镇,编号从 1 1 到 N N ;有 M M 条道路,编号从 1 1 到 M M 。

第 i 条道路双向连接城镇 Ai A_i 和城市 BiB_i,长度为 CiC_i。

从你选择的一个城市出发,在不多次经过同一城市的情况下,求经过的道路长度之和的最大值。

输入格式

输入以下列形式从标准输入端输入。

NN MM

A1 A_1 B1B_1 C1 C_1

⋮ \vdots

AM A_M BM B_M CM C_M

输出格式

输出答案。

样例 #1

样例输入 #1


4 4

1 2 1

2 3 10

1 3 100

1 4 1000

样例输出 #1


1110

示例 #2

样例输入 #2


10 1

5 9 1

样例输出 #2


1

示例 #3

样例输入 #3


10 13

1 2 1

1 10 1

2 3 1

3 4 4

4 7 2

4 8 1

5 8 1

5 9 3

6 8 1

6 9 5

7 8 1

7 9 4

9 10 3

样例输出 #3


20

提示

数据范围

  • 2 ≤ N ≤ 10 2\ \leq\ N\ \leq\ 10

  • 1 ≤ M ≤ N(N−1)2 1\ \leq\ M\ \leq\ \frac{N(N-1)}{2}

  • 1≤ Ai < Bi ≤ N 1\leq\ A_i\ <\ B_i\ \leq\ N

  • (Ai,Bi) (A_i,B_i) 互不相同

  • 1≤ Ci ≤ 108 1\leq\ C_i\ \leq\ 10^8

  • 所有输入都是整数

示例解释 1

如果我们移动 4→ 1→ 3→ 2 4\to\ 1\to\ 3\to\ 2 ,我们经过的道路的长度总和为 1110 1110 。

示例说明 2

可能有一些城镇没有道路连接。

示例解释 3

! \ЈFig. 1