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;
}