旅游

#include <algorithm>
#include <iostream>
#include <vector>


//并查集
class DisjointSet
{
public:
    DisjointSet(int n)
    {
        size = n+1;
        fa.resize(size);
        rank.resize(size);
        init();
    }

    int find(int x)
    {
        return fa[x] == x ? x : (fa[x] = find(fa[x]));
    }

    bool meger(int a,int b)
    {
        int x = find(a),y = find(b);
        if(x == y)
        {
            return true;
        }

        if(rank[x] > rank[y])
        {
            //简单合并到复杂
            fa[y] = x;
        }
        else
        {
            if(rank[x] == rank[y])
            {
                rank[y]+=1;
            }
            fa[x] = y;
        }
        return false;
    }

private:
    void init()
    {
        for(int i = 1;i < size;++i)
        {
            fa[i] = i;
            rank[i] = 1;
        }
    }

private:
    std::vector<int> fa; // 存储当前节点的父节点
    std::vector<int> rank; //存储当前节点的秩
    int size;
};


struct Path
{
    int x;
    int y;
    long long a;
};

int main()
{
    int n = 0,m = 0;
    long long c = 0;
    std::cin>>n>>m>>c;

    std::vector<Path> paths(m);
    for(int i = 0;i < m;++i)
    {
        auto& it = paths[i];
        std::cin>>it.x>>it.y>>it.a;
    }

    DisjointSet disjointSet(n);

    std::sort(paths.begin(),paths.end(),[](Path a,Path b){
        return a.a < b.a;
    });

    //最小生成树
    std::vector<long long> moneys;
    for(int i = 0;i < m;++i)
    {
        Path& tmp = paths[i];
        if(!disjointSet.meger(tmp.x,tmp.y))
        {
            moneys.push_back(tmp.a);
        }
    }
    std::sort(moneys.begin(),moneys.end(),std::greater<long long>());
    long long ans = 0,cur_num = 1;

    for(long long&it : moneys)
    {
        if(c - cur_num*it < 0)
        {
            ans = it;
            break;
        }
        c -= cur_num*it;
        cur_num+=1;
    }

    std::cout<<ans<<'\n';

}