#include <stdio.h>
#include <stdlib.h>
 
typedef struct Edge {
    int u, v, weight;
} Edge;
 
typedef struct Graph {
    int V, E;
    Edge* edge;
} Graph;
 
// Function to compare edges based on their weights
int cmp(const void* a, const void* b) {
    Edge* edgeA = (Edge*)a;
    Edge* edgeB = (Edge*)b;
    return edgeA->weight - edgeB->weight;
}
 
// Function to find the parent of a vertex in the DSU
int find(int parent[], int i) {
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}
 
// Function to union two vertices in the DSU
void unionSet(int parent[], int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}
 
// Function to implement Kruskal's Algorithm
void kruskal(Graph* graph) {
    int V = graph->V;
    Edge result[V];
    int e = 0;
    int i = 0;
 
    // Sort all edges in non-decreasing order of their weights
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), cmp);
 
    // Create a DSU data structure
    int* parent = (int*)malloc(V * sizeof(int));
    for (int v = 0; v < V; v++)
        parent[v] = -1;
 
    // Iterate through all edges
    while (e < V - 1 && i < graph->E) {
        Edge next_edge = graph->edge[i++];
 
        int x = find(parent, next_edge.u);
        int y = find(parent, next_edge.v);
 
        // If the two vertices are not in the same connected component
        if (x != y) {
            result[e++] = next_edge;
            unionSet(parent, x, y);
        }
    }
 
    // Print the MST
    printf("The edges of Minimum Cost Spanning Tree are:\n");
    for (int j = 0; j < e; j++)
        printf("Edge cost from %d to %d: %d\n", result[j].u, result[j].v, result[j].weight);
 
    printf("Minimum cost of spanning tree = %d\n", result[e - 1].weight);
}
 
int main() {
    int V, E;
    printf("Enter the number of vertices: ");
    scanf("%d", &V);
 
    printf("Enter the number of edges: ");
    scanf("%d", &E);
 
    Graph* graph = createGraph(V, E);
 
    printf("Enter the edges (source destination weight):\n");
    for (int i = 0; i < E; i++) {
        scanf("%d%d%d", &graph->edge[i].u, &graph->edge[i].v, &graph->edge[i].weight);
    }
 
    // Find and print the MST using Kruskal's Algorithm
    kruskal(graph);
 
    return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCnR5cGVkZWYgc3RydWN0IEVkZ2UgewogICAgaW50IHUsIHYsIHdlaWdodDsKfSBFZGdlOwoKdHlwZWRlZiBzdHJ1Y3QgR3JhcGggewogICAgaW50IFYsIEU7CiAgICBFZGdlKiBlZGdlOwp9IEdyYXBoOwoKLy8gRnVuY3Rpb24gdG8gY29tcGFyZSBlZGdlcyBiYXNlZCBvbiB0aGVpciB3ZWlnaHRzCmludCBjbXAoY29uc3Qgdm9pZCogYSwgY29uc3Qgdm9pZCogYikgewogICAgRWRnZSogZWRnZUEgPSAoRWRnZSopYTsKICAgIEVkZ2UqIGVkZ2VCID0gKEVkZ2UqKWI7CiAgICByZXR1cm4gZWRnZUEtPndlaWdodCAtIGVkZ2VCLT53ZWlnaHQ7Cn0KCi8vIEZ1bmN0aW9uIHRvIGZpbmQgdGhlIHBhcmVudCBvZiBhIHZlcnRleCBpbiB0aGUgRFNVCmludCBmaW5kKGludCBwYXJlbnRbXSwgaW50IGkpIHsKICAgIGlmIChwYXJlbnRbaV0gPT0gLTEpCiAgICAgICAgcmV0dXJuIGk7CiAgICByZXR1cm4gZmluZChwYXJlbnQsIHBhcmVudFtpXSk7Cn0KCi8vIEZ1bmN0aW9uIHRvIHVuaW9uIHR3byB2ZXJ0aWNlcyBpbiB0aGUgRFNVCnZvaWQgdW5pb25TZXQoaW50IHBhcmVudFtdLCBpbnQgeCwgaW50IHkpIHsKICAgIGludCB4c2V0ID0gZmluZChwYXJlbnQsIHgpOwogICAgaW50IHlzZXQgPSBmaW5kKHBhcmVudCwgeSk7CiAgICBwYXJlbnRbeHNldF0gPSB5c2V0Owp9CgovLyBGdW5jdGlvbiB0byBpbXBsZW1lbnQgS3J1c2thbCdzIEFsZ29yaXRobQp2b2lkIGtydXNrYWwoR3JhcGgqIGdyYXBoKSB7CiAgICBpbnQgViA9IGdyYXBoLT5WOwogICAgRWRnZSByZXN1bHRbVl07CiAgICBpbnQgZSA9IDA7CiAgICBpbnQgaSA9IDA7CgogICAgLy8gU29ydCBhbGwgZWRnZXMgaW4gbm9uLWRlY3JlYXNpbmcgb3JkZXIgb2YgdGhlaXIgd2VpZ2h0cwogICAgcXNvcnQoZ3JhcGgtPmVkZ2UsIGdyYXBoLT5FLCBzaXplb2YoZ3JhcGgtPmVkZ2VbMF0pLCBjbXApOwoKICAgIC8vIENyZWF0ZSBhIERTVSBkYXRhIHN0cnVjdHVyZQogICAgaW50KiBwYXJlbnQgPSAoaW50KiltYWxsb2MoViAqIHNpemVvZihpbnQpKTsKICAgIGZvciAoaW50IHYgPSAwOyB2IDwgVjsgdisrKQogICAgICAgIHBhcmVudFt2XSA9IC0xOwoKICAgIC8vIEl0ZXJhdGUgdGhyb3VnaCBhbGwgZWRnZXMKICAgIHdoaWxlIChlIDwgViAtIDEgJiYgaSA8IGdyYXBoLT5FKSB7CiAgICAgICAgRWRnZSBuZXh0X2VkZ2UgPSBncmFwaC0+ZWRnZVtpKytdOwoKICAgICAgICBpbnQgeCA9IGZpbmQocGFyZW50LCBuZXh0X2VkZ2UudSk7CiAgICAgICAgaW50IHkgPSBmaW5kKHBhcmVudCwgbmV4dF9lZGdlLnYpOwoKICAgICAgICAvLyBJZiB0aGUgdHdvIHZlcnRpY2VzIGFyZSBub3QgaW4gdGhlIHNhbWUgY29ubmVjdGVkIGNvbXBvbmVudAogICAgICAgIGlmICh4ICE9IHkpIHsKICAgICAgICAgICAgcmVzdWx0W2UrK10gPSBuZXh0X2VkZ2U7CiAgICAgICAgICAgIHVuaW9uU2V0KHBhcmVudCwgeCwgeSk7CiAgICAgICAgfQogICAgfQoKICAgIC8vIFByaW50IHRoZSBNU1QKICAgIHByaW50ZigiVGhlIGVkZ2VzIG9mIE1pbmltdW0gQ29zdCBTcGFubmluZyBUcmVlIGFyZTpcbiIpOwogICAgZm9yIChpbnQgaiA9IDA7IGogPCBlOyBqKyspCiAgICAgICAgcHJpbnRmKCJFZGdlIGNvc3QgZnJvbSAlZCB0byAlZDogJWRcbiIsIHJlc3VsdFtqXS51LCByZXN1bHRbal0udiwgcmVzdWx0W2pdLndlaWdodCk7CgogICAgcHJpbnRmKCJNaW5pbXVtIGNvc3Qgb2Ygc3Bhbm5pbmcgdHJlZSA9ICVkXG4iLCByZXN1bHRbZSAtIDFdLndlaWdodCk7Cn0KCmludCBtYWluKCkgewogICAgaW50IFYsIEU7CiAgICBwcmludGYoIkVudGVyIHRoZSBudW1iZXIgb2YgdmVydGljZXM6ICIpOwogICAgc2NhbmYoIiVkIiwgJlYpOwoKICAgIHByaW50ZigiRW50ZXIgdGhlIG51bWJlciBvZiBlZGdlczogIik7CiAgICBzY2FuZigiJWQiLCAmRSk7CgogICAgR3JhcGgqIGdyYXBoID0gY3JlYXRlR3JhcGgoViwgRSk7CgogICAgcHJpbnRmKCJFbnRlciB0aGUgZWRnZXMgKHNvdXJjZSBkZXN0aW5hdGlvbiB3ZWlnaHQpOlxuIik7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IEU7IGkrKykgewogICAgICAgIHNjYW5mKCIlZCVkJWQiLCAmZ3JhcGgtPmVkZ2VbaV0udSwgJmdyYXBoLT5lZGdlW2ldLnYsICZncmFwaC0+ZWRnZVtpXS53ZWlnaHQpOwogICAgfQoKICAgIC8vIEZpbmQgYW5kIHByaW50IHRoZSBNU1QgdXNpbmcgS3J1c2thbCdzIEFsZ29yaXRobQogICAga3J1c2thbChncmFwaCk7CgogICAgcmV0dXJuIDA7Cn0=