Description

城市 C 是一个非常繁忙的大都市, 城市中的道路十分的拥挤, 于是市长决定对其中的道路进行 改造. 城市 C 的道路是这样分布的: 城市中有 \(n\) 个交叉路口, 有些交叉路口之间有道路相连, 两个交叉路口之间最多有一条道路相连接. 这些道路是双向的, 且把所有的交叉路口直接或间接的连接起来了. 每条道路都有一个分值, 分值越小表示这个道路越繁忙, 越需要进行改造. 但是市政府的资金有限, 市长希望进行改造的道路越少越好, 于是他提出下面的 要求:

  1. 改造的那些道路能够把所有的交叉路口直接或间接的连通起来.
  2. 在满足要求 1 的情况下, 改造的道路尽量少.
  3. 在满足要求 1, 2 的情况下, 改造的那些道路中分值最大的道路分值尽量小.

作为市规划局的你, 你应当作出最佳的决策, 选择那些道路应当被修建.

Input

第一行有两个整数 \(n, m\) 表示城市有 \(n\) 个交叉路口,\(m\) 条道路.

接下来 \(m\) 行是对每条道路的描述,\(u, v, c\) 表示交叉路口 \(u\) 和 \(v\) 之间有道路相连, 分值为 \(c\).

Output

两个整数 \(s, max\), 表示你选出了几条道路, 分值最大的那条道路的分值是多少.

Sample Input

4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8

Sample Output

3 6

Data Range

对于所有的数据, 满足:\(1 \leq n \leq 300, 1 \leq c \leq 10000\)

Explanation

最小瓶颈生成树就是最小生成树, 因为 Kruskal 和 Prim 都是这样贪心求的最小生成树. 其实就是一道模板题.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 310, maxm = 100100;

class UnionFindSet
{
public:
    int n, par[maxn];
    int find(int p)
    {
        if (par[p] == p)
            return p;
        return par[p] = find(par[p]);
    }
    void join(int p, int q)
    {
        p = find(p);
        q = find(q);
        par[p] = q;
        return ;
    }
    void init(int n_)
    {
        n = n_;
        for (int i = 1; i <= n; i++)
            par[i] = i;
        return ;
    }
} ufs;

struct edge {
    int u, v, len;
    edge *next; };
bool cmp(edge a, edge b) {
    return a.len < b.len; }

class MinimumSpanTree
{
public:
    int n, ecnt;
    edge *edges[maxn], epool[maxm];
    void add_edge(int u, int v, int len)
    {
        edge *p = &epool[++ecnt];
        p->u = u; p->v = v; p->len = len;
        p->next = edges[u]; edges[u] = p;
        return ;
    }
    int eval(void)
    {
        int res = 0;
        sort(epool + 1, epool + 1 + ecnt, cmp);
        ufs.init(n);
        for (int i = 1; i <= ecnt; i++) {
            int p = epool[i].u,
                q = epool[i].v;
            p = ufs.find(p);
            q = ufs.find(q);
            if (p == q)
                continue;
            ufs.join(p, q);
            res = max(res, epool[i].len);
        }
        return res;
    }
} graph;

int n, m;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    graph.n = n;
    for (int i = 1, a, b, c; i <= m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        graph.add_edge(a, b, c);
    }
    int res = graph.eval();
    printf("%d %d\n", n - 1, res);
    return 0;
}