Description

Given an undirected graph, find a cycle that contains at least $3$ vertices, with no repeated vertices on the cycle, and whose total edge length is minimal. This problem is called the minimum cycle problem in an undirected graph. In this task, you need to output the total edge weight of the minimum cycle. If there is no solution, output No solution..

Input Format

The first line contains two positive integers $n, m$, representing the number of vertices and the number of edges.

The next $m$ lines each contain three positive integers $u, v, d$, indicating that there is an edge of length $d$ between vertices $u$ and $v$.

Output Format

Output the total edge weight of the cycle with the minimum total edge weight. If there is no solution, output No solution..

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

61

Hint

Sample explanation: one feasible solution is $1-3-5-2-1$.

For $20\%$ of the testdata, $n, m \leq 10$.

For $60\%$ of the testdata, $m \leq 100$.

For $100\%$ of the testdata, $1 \le n \leq 100$, $1 \le m \leq 5 \times 10^3$, $1 \leq d \leq 10^5$.

The output for no solution includes a period.

Translated by ChatGPT 5