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