# Tree/Graph problem help

Hello. The original problem is in chinese so i translated it. I don’t understand this problem’s logic and how im going to solve it What does k do? How to distinguish which “category” of regret a relationship belongs to? Then why is the sample output 18 and not 15?

[Problem description]
In Little F’s memory, there are a total of N things that left her with deep regrets. Things are related. There are M sets of relations related to these N things, and the i-th group of relations is related to the ui-th thing and the vi-th thing. Each set of relationships brings some regret to little F, and the regret value of the i-th set of relationships is pi . Regrets are also different. According to the different results of the regret value modulo k , relationships can be divided into k categories. Little F wants to select several sets of relationships so that all N things are directly or indirectly related. In order to no longer leave any regrets, Little F requires that each category of regrets be selected from one group to one group. when the above conditions are met, what is the minimum sum of regret values ​​of the relationship selected by small F?
[Input format]
Enter a total of M + 1 lines. The first line of input contains three integers N, M, k. The next M lines, each with three integers ui, vi, pi , describe a set of relationships.
[Output format]
Output an integer in one line, representing the minimum value of the sum of regret values ​​of the relationship selected by small F.
[Sample 1 input]
5 7 4
1 2 1
2 3 2
1 3 3
3 4 8
4 5 4
3 5 20
2 4 100
[Sample 1 output]
18

The sentence

Little F requires that each category of regrets be selected from one group to one group.

is a bit confusing, but from what I can tell:

1. You are given a weighted undirected graph
2. You wanted to find the minimum spanning tree.
3. The edges can be separated into different sets based on their weight mod k. The problem requires that your minimum spanning tree contain at least one edge from each of the k residue groups of edges.

For the sample case, as I’m sure you found, the minimum spanning tree gives total minimum weight of 15. However, this MST would not have any edges that are 3 mod 4. Therefore, you need to include the edge from 1 to 3 of weight 3, making the overall sum 18.