Minimum Weight Cycle in an Undirected weighted Graph

Given an integer A, representing number of vertices in a graph.
Given a matrix of integers B of size N x 3 where N represents number of Edges in a Graph and
Triplet (B[i][0], B[i][1], B[i][2]) implies there is an undirected edge between B[i][0] and B[i][1]
and weight of that edge is B[i][2].

Find and return the weight of minimum weighted cycle and if there is no cycle return -1 instead.

Note: Graph may contain multiple edges and self loops.



Input Format

The first argument given is the integer A.
The second argument given is the integer matrix B.

Output Format

Return the weight of minimum weighted cycle and if there is no cycle return -1 instead.	

Constraints

1 <= A <= 1000
1 <= B[i][0], B[i][1] <= A
1 <= B[i][2] <= 100000

For Example

Input 1:
    A = 4
    B = [   [1 ,2 ,2]
            [2 ,3 ,3]
            [3 ,4 ,1]
            [4 ,1 ,4]
            [1 ,3 ,15]  ]
Output 1:
    10 

Explanation:
    Given graph forms 3 cycles
    1. 1 ---> 2 ---> 3 ---> 4 ---> 1 weight = 10
    2. 1 ---> 2 ---> 3 ---> 1 weight = 20
    3. 1 ---> 3---> 4 ---> 1 weight = 20
    so answer would be 10.
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Minimum Weight Cycle in an Undirected weighted Graph on Interview Code Editor
Sign Up
to access hints and editorial solutions for Minimum Weight Cycle in an Undirected weighted Graph

Discussion


Loading...
Click here to start solving coding interview questions