c国边防军在边境某处的阵地是由n个地堡组成的。工兵连受命来到阵地要进行两期施工。

第一期的任务是挖掘暗道让所有地堡互联互通。现已勘测设计了m条互不相交的暗道挖掘方案，如果这m条暗道都实施挖掘，肯定能达到互联互通的目的。事实上，适当选择其中n-1个方案挖掘，就能实现互联互通，即从每个地堡出发都能到达其他任何一个地堡（允许经过别的地堡）。

连长精心谋算，在m个设计规划中选取了挖掘总距离最短且能保证互联互通的若干个暗道规划实施了挖掘，完成了第一期的施工任务后又接受了第二期的施工任务，要求选择一个地堡进行扩建改造，使其能向每个地堡提供弹药。为了让弹药供应更及时、更快捷，从改扩建的地堡到最远地堡的距离（称为最远输送距离）应当尽量小。

你的任务是先求出第一期施工挖掘的总距离，再求改扩建地堡最远输送距离的最小值。

输入描述

输出描述

样例输入

样例输出

数据范围及提示

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const long N = 100100, M = 200100;
struct ty
{
    long x, y, l;
    bool operator < (const ty &a) const
    {
        if (l < a.l) return true;
			else return false;
    }
}edge[M];
struct ty2
{
    long t, w, next;
}edgenew[M];
long n, m, mm, summ, maxn, dian, re;
long fa[N];
long head[N];
long dist[N];
long pre[N];
bool v[N];
long const INF = 1000000;

void init()
{
    memset(edge, 0 ,sizeof(edge));
    scanf("%d%d", &n, &m);
    for (long i = 0; i < m; i++)
    {
        scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].l);
    }
}
void prepare()
{
    sort (edge, edge + m);
    for (long i = 1; i <= n; i++)
        fa[i] = i;
}
void insertedge(long x, long y, long z, long k)
{
    edgenew[k].t = y;
    edgenew[k].next = head[x];
    edgenew[k].w = z;
    head[x] = k;
}
long findfa(long x)
{
   return fa[x] == x ? x : (fa[x] = findfa(fa[x]));
}
void merge(long x, long y)
{
    fa[findfa(x)] = findfa(y);
}

void kruskal()
{
    long cnt = 0;
    mm = 0;
    long long sum = 0;
    for (long i = 0; i < m; i++)
    {
        long fx = findfa(edge[i].x);
        long fy = findfa(edge[i].y);
        if (fx != fy)
        {
            merge(fx, fy);
            cnt++;
            mm++;
            insertedge(edge[i].x, edge[i].y, edge[i].l, mm);
            mm++;
            insertedge(edge[i].y, edge[i].x, edge[i].l, mm);
            sum += edge[i].l;
            if (cnt >= n - 1) break;
        }
    }
    cout << sum<<endl;
}

void dfs(long x)
{
    long i = head[x];
    for (long i = head[x]; i != 0; i = edgenew[i].next)
        if (!v[edgenew[i].t])
        {
            v[edgenew[i].t] = true;
            pre[edgenew[i].t] = x;
            dist[edgenew[i].t] = dist[x] + edgenew[i].w;
            dfs(edgenew[i].t);
            v[edgenew[i].t] = false;
        }
}
void dfs2(long x)
{
    if (pre[x] != 0) dfs2(pre[x]);
    if ((dist[x] >= maxn / 2.0) && (re > dist[x]))
    {
        re = dist [x];
    }
     if ((maxn - dist[x] >= maxn / 2.0) && (re > maxn - dist[x]))
    {
        re = maxn - dist[x];
    }
}
int main()
{
    freopen("1700.in", "r", stdin);
    freopen("1700.out", "w", stdout);
    init();
    prepare();
    kruskal();
    ///带权中位数
    memset(dist, 0, sizeof(dist));
    memset(v, 0, sizeof(v));
    v[1] = true;
    dfs(1);
    maxn = 0, dian = 0;
    for (long i =1; i<=n ;i++)
    {
        if (dist[i] > maxn)
        {
            maxn = dist[i];
            dian = i;
        }
    }

    memset(dist, 0, sizeof(dist));
    memset(pre, 0, sizeof(pre));
    memset(v, 0, sizeof(v));
    v[dian] = true;
    dfs(dian);

    maxn = 0; dian = 0;
    for (long i = 1; i <= n ;i++)
    {
        //cout << dist[i]<<' ';
        if (dist[i] > maxn)
        {
            maxn = dist[i];
            dian = i;
        }
    }
    re = maxn;
    dfs2(dian);

   // cout << maxn << endl;
    cout << re << endl;
    return 0;
}