Maximum Weighted Perfect Matching in a Bipartite Graph

You are given a bipartite graph with two sets of vertices, each containing \( n \) vertices. There are \( m \) weighted edges connecting vertices from the left set to the right set. It is guaranteed that there exists at least one perfect matching.

Your task is to find a perfect matching such that the sum of the weights of the chosen edges is maximized.

Note: A perfect matching is a set of \( n \) edges in which every vertex appears exactly once. Each edge is represented by three numbers \( u, v, w \) meaning there is an edge from vertex \( u \) (in the left set) to vertex \( v \) (in the right set) with weight \( w \).

The desired output is the maximum sum of weights followed by a matching scheme: a list of \( n \) integers where the \( i\)-th integer represents the index of the vertex in the right part that the \( i\)-th vertex in the left part is matched with.

inputFormat

The first line contains two integers \( n \) and \( m \) \( (1 \leq n \leq ? , 1 \leq m \leq ? ) \) indicating the number of vertices in each part and the number of edges, respectively. Each of the following \( m \) lines contains three integers \( u, v, w \) where \( 1 \leq u, v \leq n \) and \( w \) is the weight of the edge connecting vertex \( u \) in the left part and vertex \( v \) in the right part.

outputFormat

Output two lines. The first line should contain a single integer representing the maximum sum of weights in a perfect matching. The second line should contain \( n \) space-separated integers where the \( i\)-th integer denotes the index of the vertex in the right part that is matched with the \( i\)-th vertex in the left part. If there are multiple solutions, any one will be accepted.

sample

2 4
1 1 5
1 2 1
2 1 2
2 2 4

9
1 2