Smallest Cycle in a Weighted Undirected Graph

You are given an undirected weighted graph with N nodes and M edges. Each edge connects two distinct nodes and carries a positive weight. Your task is to find the cycle with the smallest total weight in the graph. A cycle is defined as a sequence of nodes \(v_1, v_2, \dots, v_k\) (with \(k \ge 3\)) such that there is an edge between \(v_i\) and \(v_{i+1}\) for all \(1 \le i < k\) and also an edge between \(v_k\) and \(v_1\). The weight of the cycle is given by the sum of the weights of its edges, i.e., \(\sum_{i=1}^{k} w_{e_i}\). If no cycle exists in the graph, output -1.

inputFormat

The first line of input contains two space-separated integers \(N\) and \(M\), indicating the number of nodes and edges respectively. Each of the following \(M\) lines contains three space-separated integers \(u\), \(v\), and \(w\), representing an undirected edge between nodes \(u\) and \(v\) with weight \(w\). Nodes are labeled from 1 to \(N\).

outputFormat

Output a single integer representing the weight of the smallest cycle in the graph. If no cycle exists, output -1.

3 3
1 2 1
2 3 2
3 1 2

5