Minimum Cycle in an Undirected Graph

You are given an undirected graph. Your task is to find a simple cycle (a cycle that does not contain any repeated nodes) containing at least \(3\) nodes such that the sum of the weights of the edges in the cycle is minimized. This problem is known as the Minimum Cycle Problem for undirected graphs.

If there is no cycle with at least 3 nodes, output No solution.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of nodes and the number of edges in the graph respectively. Nodes are numbered from 1 to \(n\).

Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(w\), indicating there is an undirected edge between nodes \(u\) and \(v\) with weight \(w\).

outputFormat

Output a single integer representing the minimum sum of the weights of the cycle. If there is no cycle containing at least 3 distinct nodes, output No solution.

sample

4 4
1 2 1
2 3 2
3 4 1
4 1 2

6