//struct for subsets used in MST Kruskal algoritm
typedef struct subset {
    int parent;
    int rank;
} subset_t, *subset_p;

//struct for storing graph edges
typedef struct edges {
    int src;
    int dest;
    int weight;
} edges_t, *edges_p;

//struct for storing weights and number of their occuriences
typedef struct weights {
    int weight;
    int occurCount;
} weights_t, *weights_p;

//struct to store all built trees
typedef struct trees {

    int totalWeight; // total tree weight
    int mostOccurNumber; // highest number of repeated edges for a tree
} trees_t, *trees_p;

//find and union function prototypes
int find(struct subset subsets[], int i);
void Union(struct subset subsets[], int x, int y);

#include <stdio.h>
#include <stdlib.h>
#include "header.h"

//find function used in Kruskals algorithm
int find(subset_p subsets, int i) {
    if (subsets[i].parent != i) {
        subsets[i].parent = find(subsets, subsets[i].parent);
    }
    return subsets[i].parent;
}

//union function used in Kruskals algorithm
void Union(subset_p subsets, int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank) {
        subsets[xroot].parent = yroot;
    } else if (subsets[xroot].rank > subsets[yroot].rank) {
        subsets[yroot].parent = xroot;
    } else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}
//compare function used in qsort(). Sorts all edges by ascending weight
int myComp1 (const void *a, const void *b)
{
    const edges_t * ptr_a = (const edges_t *)a;
    const edges_t * ptr_b = (const edges_t *)b;
    if (ptr_a->weight < ptr_b->weight) return -1;
    if (ptr_a->weight > ptr_b->weight) return 1;
    return 0;
}
//Sorts all present weights by descending number of occuriences in the MST
int myComp2 (const void *a, const void *b)
{
    const weights_t * ptr_a = (const weights_t *)a;
    const weights_t * ptr_b = (const weights_t *)b;
    if (ptr_a->occurCount > ptr_b->occurCount) return -1;
    if (ptr_a->occurCount < ptr_b->occurCount) return 1;
    return 0;
}
//Sorts all present MSTs primarily by descending number of same-weight occuriences
//Secondly by ascending weights
int myComp3 (const void *a, const void *b)
{
    const weights_t * ptr_a = (const weights_t *)a;
    const weights_t * ptr_b = (const weights_t *)b;
    int diff = ptr_b->occurCount - ptr_a->occurCount;
    if (diff == 0) {
        if (ptr_a->weight < ptr_b->weight) {
            diff = -1;
        } else if (ptr_a->weight > ptr_b->weight) {
            diff =  1;
        } else diff = 0;
    }
    return diff;
}

int main() {
    //number of vertices and edges for a graph
    int num_vertices, num_edges;
    scanf("%d%d", &num_vertices, &num_edges);

    // struct to keep all graph edges
    edges_p allEdges = (edges_p)malloc(num_edges*sizeof(edges_t));

    //input variables for source vertex, destanation vertex and weight of the edge
    int curr_src, curr_dest, curr_weight;

    //array to store all present (different!) weight values
    int * weights = (int *)malloc(num_edges*sizeof(int));

    //a variable to store number of elements in 'weights' array - number of different weight values in a graph
    int newWeightIndex = 0;

    //inputing data about graph edges: source vertex, destination vertex, weight
    for (int i = 0; i < num_edges; i++) {
        scanf("%d%d%d", &curr_src, &curr_dest, &curr_weight);

        //filling array of structs with input info
        allEdges[i].src = curr_src - 1;
        allEdges[i].dest = curr_dest - 1;
        allEdges[i].weight = curr_weight;

        //'Weights' array contains all weights that are present in a graph.
        //Here we decide whether we should put current weight value into an array.
        bool alreadyHasWeight = 0;
        for (int j = 0; j < i; j++) {
            if (weights[j] == curr_weight) {
                alreadyHasWeight = 1;
                break;
            }
        }
        if (alreadyHasWeight == 0) {
            weights[newWeightIndex] = curr_weight;
            newWeightIndex++;
        }
    }
    // end of data input

    //an array of structs to store info about build MSTs (the weight of MST and maximum number of edges with same weights)
    trees_p myTrees = (trees_p)malloc(newWeightIndex * sizeof(trees_t));

    //Kruscal Algoritm lopp to find an MST for all present weights.
    //We take each weight in 'weights' and change the weight of every edge in a graph that has weight equal to 'weights[i]' to -1
    for (int i = 0; i < newWeightIndex; i++) {
        int minimizedWeight = weights[i];

        //array to store subsets of vertices
        subset_p subsets = (subset_p)malloc(num_vertices * sizeof(subset_t));

        //array to store MST Edges
        edges_p mstEdges = (edges_p)malloc(num_vertices*sizeof(edges_t));

        //array to store current edge
        edges_p currentEdge = (edges_p)malloc(sizeof(edges_t));

        //variable to keep the amount of weight that was subtracted (when setting some weights to -1)
        //this is done in order to restore default weights after MST build finishes
        int subtractedWeight = 0;

        //variable to keep the number of edges which weight was changed to -1
        int infEdgesTotal = 0;

        //variable to keep the number of edges which weight was changed to -1 included to MST
        int infEdgesTaken = 0;

        //setting minimum weights
        for (int i = 0; i < num_edges; i++) {
            if (allEdges[i].weight == minimizedWeight) {
                allEdges[i].weight = -1;
                subtractedWeight += minimizedWeight+1;
                infEdgesTotal++;
            }
        }

        //sorting all graph edges in ascending order
        qsort(allEdges, num_edges, sizeof(edges_t), myComp1);

        //the kruskal algoritm itself - BEGINNING
        for (int v = 0; v < num_vertices; v++) {
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }

        int e = 0;
        int currentIndex = 0;
        int mstWeight = 0;
        int mstEdgesCount = 0;
        while (e < num_vertices - 1) {

            currentEdge[0].src = allEdges[currentIndex].src;
            currentEdge[0].dest = allEdges[currentIndex].dest;
            currentEdge[0].weight = allEdges[currentIndex].weight;

            int x = find(subsets, currentEdge[0].src);
            int y = find(subsets, currentEdge[0].dest);
            currentIndex++;

            if (x != y) {
                mstEdges[e].src = currentEdge[0].src;
                mstEdges[e].dest = currentEdge[0].dest;
                mstEdges[e].weight = currentEdge[0].weight;
                mstWeight += mstEdges[e].weight;
                mstEdgesCount++;
                if (mstEdges[e].weight == -1) {
                    infEdgesTaken++;
                }
                e++;
                Union(subsets, x, y);
            }

        }
        free(subsets);
        //the kruskal algoritm itself - END

        //Restoring default weights
        for (int i = 0; i < num_edges; i++) {
            if (allEdges[i].weight == -1) {
                allEdges[i].weight += minimizedWeight+1;
            }
        }

        //Calculating built MST weight
        mstWeight += subtractedWeight/infEdgesTotal*infEdgesTaken;

        //an array to store all weight values in MST and a number of edges in MST with that weight
        weights_p myWeights = (weights_p)malloc(mstEdgesCount*sizeof(weights_t));

        //a variable to store the number of different weight values in MST
        int num_weights = 0;

        //filling 'myWeights' array
        for(int i = 0; i < mstEdgesCount; i++) {
            myWeights[i].weight = -100;
        }
        for (int i = 0; i < mstEdgesCount; i++) {
            for (int j = 0; j < i + 1; j++) {
                if (myWeights[j].weight == -100) {
                    myWeights[j].weight = mstEdges[i].weight;
                    myWeights[j].occurCount = 1;
                    num_weights++;
                    break;
                } else if (myWeights[j].weight != mstEdges[i].weight){
                    continue;
                } else {
                    myWeights[j].occurCount++;
                    break;
                }
            }
        }

        free(currentEdge);

        //sorting all present weights by descending number of edges with that weight
        qsort(myWeights, num_weights, sizeof(weights_t), myComp2);

        //a variable to store a maximum number of weight occuriences in MST
        int mostOccs = myWeights[0].occurCount;

        free(myWeights);
        free(mstEdges);

        //adding info about current MST into 'myTrees' array
        myTrees[i].totalWeight = mstWeight;
        myTrees[i].mostOccurNumber = mostOccs;
    }
    // End of Krushkal Algorithm iteration

    free(weights);
    free(allEdges);

    //sorting 'myTrees' array to get an MST with maximum number of same-edge occuriences
    //and lowest weight in the top
    qsort(myTrees, newWeightIndex, sizeof(trees_t), myComp3);

    //outputing the result
    printf ("%d",myTrees[0].totalWeight);

    free(myTrees);
    system("pause");
    return 0;
}