Hello everyone.

Problem: Researchers from the Department of Operations Research at the University of British Columbia were contracted to a strange tarefa.Vários African countries decided to officially join and use the means of transport which became known worldwide in the Tarzan films: the vine. There are millions of vines in Africa and it is surprising speed and efficiency with which a person can move around in the jungle using this means of transportation. Only a small problema.Os came vines are dominated by three major tribes: the makelelês the malouhdás and abedis. Tribes demand to be paid by vines used in the transportation system. As they do not know the meaning of words like cartel, each one made ​​his price, and diverged considerably. While the 1235 makelelês require bongos by creeper used, require malouhdás abedis 8977 and 10 923 (Jane is still alive, and helped broker the negotiations for this tribe). The researchers were hired to pick the vines that make up the first system cipoviário the world. The contractors have built millions of "points liana" the African jungle and want the vines are chosen such that it is possible to go from any point to any other contractors using the vines (you may have to change sometimes vine, as did Tarzan). You should say what the cost of a system that meets these requirements and be as cheap as possible. You can assume that there are enough vines in the jungle so that whenever there is a system that meets the requirements cipoviário.

Input: The input consists of several instances. The first line of each instance contains two integers n (1 <= n <= 1000) in (1 <= m <= 2000000), where n is the number of "points liana" is in the number of vines. Each of the following m lines contains three integers u, vec indicating that there is a vine that will point to the point u and v with cost c, where 1 <= u, v <= n and c = 1235 or 8977 or 10923.

Output: For each instance, you have to print some identificator instance k, where k is the number of the actual instance. Next line print the cost of the system who reach the descripted requisits.

Input:
3 3
1 2 10923
1 3 1235
2 3 1235
3 2
1 2 1235
2 3 10923

Output:
Instance 1
2470

Instance 2
12158

I need to solve using a Minimum Spanning Tree, which connect all points with minimum cost.

Code below:

#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <string>
#include <stdlib.h>
#include <vector>

#define INF 9999999999
#define ll long long int

using namespace std;

struct UnionFind {
    ll N, *id, *size;
    UnionFind(ll n) {
        this->N = n;
        id = new ll[n];
        size = new ll[n];
        for(ll i = 0; i < n; i++) {
            id[i] = i;
            size[i] = 1;
        }
    }

    ll root(ll i) {
        while(i != id[i]) {
            id[i] = id[id[i]];
            i = id[i];
        }
        return i;
    }

    bool find(ll p, ll q) {
        return (root(p) == root(q));
    }

    void unite(ll p, ll q) {
        ll i = root(p);
        ll j = root(q);
        if(i != j) {
            if(size[i] < size[j]) {
                id[i] = j;
                size[j] += size[i];
            } else {
                id[j] = i;
                size[i] += size[j];
            }
        }
    }
};

struct edge {
    ll x, y, weight;

    edge(ll _x, ll _y, ll _weight) {
        x = _x;
        y = _y;
        weight = _weight;
    }

    edge(){};
};

ll n, m, xx, yy, weight, instance = 1;
edge low[2000001], mid[2000001], high[2000001];

int main(void) {
    freopen("in.in.c", "r", stdin);
    while(~scanf("%d%d", &n, &m)) {
        int idxLow = 0, idxMid = 0, idxHigh = 0;
        ll dist = 0;
        printf("Instancia %d\n", instance++);
        UnionFind uf(n + 1);
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &xx, &yy, &weight);
            if(weight == 1235) {
                low[idxLow++] = edge(xx, yy, weight);
            } else if(weight == 8977) {
                mid[idxMid++] = edge(xx, yy, weight);
            } else {
                high[idxHigh++] = edge(xx, yy, weight);
            }
        }
        for(int i = 0; i < idxLow; i++) {
            edge tmp = low[i];
            int x = tmp.x;
            int y = tmp.y;
            ll weigh = tmp.weight;
            if(!uf.find(x, y)) {
                uf.unite(x, y);
                dist += weigh;
            }
        }
        for(int i = 0; i < idxMid; i++) {
            edge tmp = mid[i];
            int x = tmp.x;
            int y = tmp.y;
            ll weigh = tmp.weight;
            if(!uf.find(x, y)) {
                uf.unite(x, y);
                dist += weigh;
            }
        }
        for(int i = 0; i < idxHigh; i++) {
            edge tmp = high[i];
            int x = tmp.x;
            int y = tmp.y;
            ll weigh = tmp.weight;
            if(!uf.find(x, y)) {
                uf.unite(x, y);
                dist += weigh;
            }
        }
        printf("%d\n\n", dist);
    }
    return 0;
}

Accepted.
1) Create three arrays, one for the loweest values, one for mid values and otther for high values. (it simulate the sort)
2) Put each "edge" in your respective array.
3) Use Krukson algorithm to solve. (Minimum Spanning Tree)