Galia

#include <cstdio>
#include <cstdlib>

const int nMax = 101, mMax = 1000;
int nodes, edges, selected;
struct edge {
    int x, y, c;
} edgeVec[mMax], edgeSel[mMax];
bool viz[nMax], vizEdge[mMax];

void read()
{
    freopen("galia.in", "rt", stdin);
    freopen("galia.out", "wt", stdout);
    scanf("%d %d", &nodes, &edges);
    for (int i = 0; i < edges; i++) {
        scanf("%d %d %d", &edgeVec[i].x, &edgeVec[i].y, &edgeVec[i].c);
    }
}

int compare(const void* first, const void* second)
{
    return ((edge*)first)->c - ((edge*)second)->c;
}

void prim()
{
    edgeSel[selected++] = edgeVec[0];
    viz[edgeVec[0].x] = viz[edgeVec[0].y] = 1;
    while (selected < nodes - 1) {
        for (int i = 1; i < edges; i++) {
            if (viz[edgeVec[i].x] && !viz[edgeVec[i].y]) {
                edgeSel[selected++] = edgeVec[i];
                viz[edgeVec[i].y] = 1;
                vizEdge[i] = 1;
            } else if (!viz[edgeVec[i].x] && viz[edgeVec[i].y]) {
                edgeSel[selected++] = edgeVec[i];
                viz[edgeVec[i].x] = 1;
                vizEdge[i] = 1;
            }
        }
    }
}

void write()
{
    printf("%d\n", selected);
    for (int i = 0; i < selected; i++) {
        printf("%d %d\n", edgeSel[i].x, edgeSel[i].y);
    }
}

void solve()
{
    edge temp;
    qsort(edgeVec, edges, sizeof(edge), compare);
    prim();
    write();
    // de aici nu se stie :))
    fclose(stdin);
    fclose(stdout);
}

int main()
{
    read();
    solve();
    return 0;
}