Micro and Graph

3.5

2 votes
Medium
Problem

Micro is having a graph containing N vertices and M edges, each edge is having an associated weight. He knows for sure that the graph contains several Hamiltonian Paths (path that visits all the vertices exactly once). He challenged his friend to find out the minimum element of the array which stores the strength of all Hamiltonian Paths in the graph. Strength of a Hamiltonian Path is the sum of weight of edges in that path. But Micro himself does not know the answer to it. Help Micro in solving this problem.

Input:
First line consists of two space separated integers denoting N and M.
Each of the following M lines consists of three space separated integers X, Y and Z denoting that there is an edge between vertices X and Y having weight Z.

Output:
Print the answer in a new line.

Constraints:
1N10
1M20
1X,YN
1Z100

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

There are two Hamiltonian Paths in the given graph.
1 - 2 - 3 - 4 (Strength = 10)
1 - 2 - 4 - 3 (Strength = 7)
So, array will have two elements {10, 7}, so the answer is clearly 7

Editor Image

?