ololo.cpp
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <cstring>
#include <string>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FI(i,b) FOR(i,0,b)
#define V(t) vector < t >
#define pb push_back
#define MEMS(a,b) memset((a),(b),sizeof(a))
#define U unsigned
#define LL long long
using namespace std;
int n,m;
struct edge
{
int u,v,l;
edge(){};
edge(int uu, int vv, int ll):u(uu),v(vv),l(ll){};
};
bool comp(const edge& a, const edge& b)
{
return a.l < b.l;
}
edge e[1000100];
int esz;
V(V(int)) G;
int pr[1000100];
int dsuinit(int n)
{
FI(i,n) pr[i] = i;
}
int dsu_find(int v)
{
if (pr[v] == v) return v;
return pr[v] = dsu_find(pr[v]);
}
int dsu_unite(int u, int v)
{
u = dsu_find(u);
v = dsu_find(v);
if (rand()%2) pr[u] = v;
else pr[v] = u;
}
int timIn[2222];
int timOut[2222];
const int maxD = 14;
int par[2222][maxD];
int rmq[2222][maxD];
int was[10000100];
int dfsTime = 0;
inline int gp(int v, int eNum)
{ if (v==e[eNum].v) return e[eNum].u; return e[eNum].v; }
const int root = 0;
void dfs(int v, int p = root, int l = 0)
{
timIn[v]=++dfsTime;
par[v][0] = p;
rmq[v][0] = l;
FOR(i,1,maxD)
{
par[v][i] = par[ par[v][i-1] ][i-1];
rmq[v][i] = max( rmq[v][i-1] , rmq[ par[v][i-1] ][i-1] );
}
FI(i,G[v].size()) if (gp(v,G[v][i]) != p) dfs(gp(v,G[v][i]), v, e[G[v][i]].l);
timOut[v]=++dfsTime;
}
inline int isParent(int u, int v) // is u parent v
{
return (timIn[u] <= timIn[v] && timOut[u] >= timOut[v]);
}
int getLCA(int u, int v)
{
if (isParent(u,v)) return u;
if (isParent(v,u)) return v;
for (int i = maxD-1; i>=0; --i)
{
if (!isParent(par[u][i],v)) u = par[u][i];
}
return par[u][0];
}
int getRMQ(int u, int lca)
{
if (u == lca) return 0;
int res = 0;
for (int i = maxD-1; i>=0; --i)
{
if (!isParent(par[u][i],lca))
{
u = par[u][i];
res = max(res,rmq[u][i]);
}
}
return res = max(res, rmq[u][0]);
}
int getANS(int num)
{
int u = e[num].u;
int v = e[num].v;
int lca = getLCA(u,v);
return e[num].l + max(getRMQ(u,lca), getRMQ(v,lca));
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
esz = 0;
G.clear();
G.resize(n);
FI(i,m)
{
int u,v,l;
scanf("%d%d%d",&u,&v,&l);
--u,--v;
e[esz++]=edge(u,v,l);
}
dsuinit(n);
sort(e,e+m,comp);
LL initTree = 0;
int initMax = 0;
LL best = 1000000000ll * 1000000000ll;
int edgeCnt = 0;
FI(i,m)
{
if (dsu_find(e[i].u)!=dsu_find(e[i].v))
{
//cerr << e[i].u << ' ' << e[i].v << ' ' << e[i].l << endl;
G[e[i].u].pb(i);
G[e[i].v].pb(i);
dsu_unite(e[i].u,e[i].v);
initTree += e[i].l;
initMax = max(initMax,e[i].l);
edgeCnt++;
}
}
if (edgeCnt<n-1) {printf("disconnected\n"); continue;}
best = min(best,initTree - 2*initMax);
dfsTime = 0;
FI(i,n+1) timIn[i] = timOut[i] = 0;
dfs(root);
FI(i,m) if (e[i].l > initMax) best = min(best, initTree - getANS(i));
printf("%lld\n",best);
}
return 0;
}