4232: Remembering the Days

# Remembering the Days ### 内存 1024MB ### 时间 2S ## 题目描述 一个地区有 $N$ 个城镇，编号从 $1$ 到 $N$，以及 $M$ 条道路，编号从 $1$ 到 $M$。 第 $i$ 条道路双向连接城镇 $A_i$ 和城镇 $B_i$，长度为 $C_i$。 从任意一个城镇出发，到达另一个城镇，同一条道路不经过两次，求可能经过的道路总长度的最大值。 ## 输入格式 输入从标准输入中按以下格式给出： $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 ``` ### 输入样例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 ``` ## 数据范围与提示 【样例1说明】 如果按 4→1→3→2 的顺序旅行，你经过的道路总长度为 1110。 【样例2说明】 可能存在没有与任何道路相连的城镇。 【样例3说明】  【数据范围】 - $2 ≤ N ≤ 10$ - $1 ≤ M ≤ N(N-1)/2$ - $1 ≤ A_i < B_i ≤ N$ - $(A_i, B_i)$ 对是互不相同的 - $1 ≤ C_i ≤ 10^8$ - 所有输入值都是整数。 【此题为代提交，评测时间会较长】 ## 题目来源 ABC317C