【Prisoning criminals】

Title description

There are two prisons in City S, which hold NN criminals, numbered 1-N1−N.The relationship between them is naturally very discordant.Many criminals even have long-standing grievances, and conflicts may break out at any time if objective conditions are met.We use "grievance value" (a positive integer value) to represent the degree of hatred between two criminals. The higher the hatred value, the more grievances between the two criminals.If two criminals with a grievance value of cc are held in the same prison, there will be friction between the two, resulting in a conflict event of influence cc.

At the end of each year, the police department will arrange a list of all conflict incidents in the prison in the current year in descending order of impact, and then report it to the mayor of City S, Z.The busy Mayor Z will only look at the impact of the first event on the list, and if the impact is bad, he will consider replacing the police chief.

After scrutinizing the conflicting relationships among the NN criminals, the police chief feels pressure.He plans to redistribute the criminals in the two prisons, in order to have less impact on the conflict, so as to keep his black gauze cap.Assuming that as long as there is hatred between two criminals in the same prison, then they will have friction at some time every year.

So, how should criminals be allocated to minimize the impact of the conflict that Mayor Z saw?What is this minimum value?

Input format

Separate two numbers on each line with a space.The first line consists of two positive integers N, MN, and M, which respectively represent the number of criminals and the number of pairs of criminals with hatred.The following MM lines each have three positive integers a_j,b_j,c_jaj​,bj​,cj​, indicating that there is hatred between criminals a_jaj​ and b_jbj​, and the resentment value is c_jcj​.The data guarantees 1

Output format

A total of 11 lines, for the impact of the conflict that Mayor Z saw.Output 0 if no conflict has occurred in the prison this year.

Sample input and output

Enter #1Copy

4 61 4 25342 3 35121 2 283511 3 66182 4 18053 4 12884

Output #1Copy

3512

Instructions/Tips

【Explanation of input and output samples】The grievance value between criminals is shown in the left picture below, and the right picture shows the distribution method of criminals. The influence of conflict events seen by the mayor is 35123512 (by No. 22 and No. 33)No. criminals trigger).No other division method is better than this one.

【Data Range】

For 30\%30% of the data there is N\leq 15N≤15.

For 70\%70% of the data there are N\leq 2000,M\leq 50000N≤2000,M≤50000.

For 100\%100% of the data there are N\leq 20000,M\leq 100000N≤20000,M≤100000.

1. The enemy of the enemy is the friend

2. You don't need to merge by rank, you can pass the test yourself, it seems to improve the speed, when the amount of data is very large.

#include #include #include int read() //Fast read, can be ignored{int ans = 0;char c = getchar();while (!isdigit(c))c = getchar();while (isdigit(c)){ans = (ans << 3) + (ans << 1) + c - '0';c = getchar();}return ans;}struct data //Save as a structure for easy sorting{int a, b, w;} C[100005];int cmp(data &a, data &b){return a.w > b.w;}int fa[40005]; //The following is a union searchint find(int a){return (fa[a] == a) ? a : (fa[a] = find(fa[a]));}int query(int a, int b){return find(a) == find(b);}void merge(int a, int b){int x=find(a);int y=find(b);fa[x]=y;}void init(int n){for (int i = 1; i <= n; ++i){fa[i] = i;}}int main(){int n = read(), m = read();init(n * 2); //For criminal i, i+n is his enemyfor (int i = 0; i < m; ++i){C[i].a = read();C[i].b = read();C[i].w = read();}std::sort(C, C + m, cmp);for (int i = 0; i < m; ++i){if (query(C[i].a, C[i].b)) // Attempt to mark two people already marked as "friends" as "enemies"{printf("%d\n", C[i].w); //The rage value at this time is the minimum value of the maximum rage valuebreak;}merge(C[i].a, C[i].b + n);merge(C[i].b, C[i].a + n);if (i == m - 1) //If there is no conflict at the end of the loop, output 0puts("0");}return 0;}