← 返回题目列表

AtCoder · abc317_c

F. 记住那些日子

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

某个区域有 N 城镇编号 1 to N,和 M 道路编号 1 to M.

的 i第条路连接城镇 A_i 和镇 B_i 双向长度 C_i.

求从您选择的城镇出发,到达另一个城镇且不多次经过同一个城镇时所经过的道路的最大可能总长度。

约束

  • 2 \leq N \leq 10
  • 1 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq A_i < B_i \leq N
  • 对 (A_i,B_i) 是不同的。
  • 1\leq C_i \leq 10^8
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

输出

打印答案。


示例输入 1

4 4
1 2 1
2 3 10
1 3 100
1 4 1000

示例输出 1

1110

如果您旅行的身份为 4\to 1\to 3\to 2,您走过的道路总长度为 1110.


示例输入 2

10 1
5 9 1

示例输出 2

1

可能有一个城镇没有与道路相连。


示例输入 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

Figure