z-cycle
You are given an undirected weighted graph with N nodes and M edges. The nodes are marked with the numbers 1 to N. Every edge connects to different nodes and has positive weights. Find the cycle with the lowest weight that contains the nodes 1 and N and whose path goes through every node at most once. A cycle is a path that goes from node 1 to node N and then goes back to 1.
InputThe data should be read from the standard input. The first line contains the integers N and M (2 <= N <= 1000, 1 <= M <= 10000), which represent the number of nodes and edges in the graph. Each of the next M lines contain the three integers X , Y and W separated by a single space (1 <= X , Y <= N, 1 <= W <= 100000), which represent an edge with weight W that connects X and Y.
OutputIn one line in the standard output, write one integer representing the weight of the cycle with the lowest weight from 1 to N. It is guaranteed that every given input will have at least one cycle.
Input:
Output:
4 6
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2
2 4 5Output:
6Explanation: the Cycle 1 -> 2 -> 4 -> 3 -> 1 is the solution, with the weight 1 + 2 + 1 + 2 = 6.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.