Градски водовод

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int id[50001];
int sz[50001];

int root(int n)
{
    while(n != id[n])
    {
        id[n] = id[id[n]];
        n = id[n];
    }
    return n;
}

bool check(int a, int b)
{
    return root(a) == root(b);
}

void join(int a, int b)
{
    a = root(a);
    b = root(b);
    if(a == b)
        return;
    if(sz[a] > sz[b])
    {
        id[b] = a;
        sz[a] += sz[b];
    }
    else
    {
        id[a] = b;
        sz[b] += sz[a];
    }
}

struct edge
{
    int a;
    int b;
    int cost;

    edge(int aa, int bb, int cc)
    {
        a = aa;
        b = bb;
        cost = cc;
    }
};

bool operator<(const edge &lhs, const edge &rhs)
{
    return lhs.cost < rhs.cost;
}

int main()
{
    for(int i = 0 ; i < 50001 ; ++i)
    {
        sz[i] = 1;
        id[i] = i;
    }

    int n,m;
    scanf("%d%d",&n,&m);

//    vector<pair<int,int> > graph[n];
    vector<edge> edges;
    for(int i = 0 ; i < m ; ++i)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        int cost = c*7 + d;
//        graph[a].push_back(make_pair(b,cost));
//        graph[b].push_back(make_pair(a,cost));
        edges.push_back(edge(a,b,cost));
    }

    sort(edges.begin(),edges.end());

    long long result = 0;

    for(int i = 0 ; i < edges.size() ; ++i)
    {
        if(!check(edges[i].a,edges[i].b))
        {
            join(edges[i].a,edges[i].b);
            result += edges[i].cost;
        }
        int temp = root(edges[i].a);
        if(sz[temp] == n)
            break;
    }

    printf("%lld",result);

    return 0;
}