#include <iostream>

using namespace std;

struct Edge
{
    int u, v, weight;
};

struct G
{
    int V, E;
    Edge* edges;
};


struct subset
{
    int rank;
    int parent;
};


int find(subset subsets[], int i)
{
    if(subsets[i].parent!=i)
    {
        i=find(subsets, subsets[i].parent);
    }
    return subsets[i].parent;
}

void Union(subset subsets[], int a, int b)
{
    int x=find(subsets, a);
    int y=find(subsets, b);
    if(x!=y)
    {
        if(subsets[x].rank<subsets[y].rank) subsets[x].parent=y;
        else
        {
            subsets[y].parent=x;
            if(subsets[x].rank==subsets[y].rank) subsets[x].rank++;
        }
    }
}

int Partition(Edge t[], int p, int r)
{
    int x=t[r].weight;
    int i, j;
    i=p-1;
    for(j=p; j<r; j++)
    {
        if(t[j].weight<x)
        {
            i++;
            swap(t[i], t[j]);
        }
    }
    swap(t[i+1], t[r]);
    return i+1;
}

void qSort(Edge t[], int p, int r)
{
    if(p<r)
    {
        int q=Partition(t, p, r);
        qSort(t, p, q-1);
        qSort(t, q+1, r);
    }
}

int Kruskal(G* graph)
{
    qSort(graph->edges, 0, graph->E-1);
    subset* subsets=new subset[graph->V];
    for(int v=0; v<graph->V; v++)
    {
        subsets[v].parent=v;
        subsets[v].rank=0;
    }
    int e=0;
    int result=0;
    for(int i=0; i<graph->E && e<graph->V-1; i++)
    {
        int x=find(subsets, graph->edges[i].u);
        int y=find(subsets, graph->edges[i].v);
        if(x!=y)
        {
            result+=graph->edges[i].weight;
            Union(subsets, x, y);
        }
    }
    return result;
}

int two_minimum(Edge tab[], int n)
{
    int x=INT_MAX, y=INT_MAX;
    for(int i=0; i<n; i++)
    {
        if(tab[i].weight<x) x=tab[i].weight;
        else if(tab[i].weight<y && tab[i].weight>=x) y=tab[i].weight;
    }
    return x+y;
}

int Low_bound(G graph)
{
    int lbound=0;
    int Edg=0;
    int current;
    for(int i=0; i<graph.V; i++)
    {
        for(int j=0; j<graph.E; j++)
        {
            if(graph.edges[j].u!=i && graph.edges[j].v!=i) Edg++;
        }
        G* new_graph=new G;
        new_graph->E=Edg;
        new_graph->V=graph.V-1;
        new_graph->edges=new Edge[new_graph->E];
        int x=0;
        int y=0;
        Edge* Deleted_Edges=new Edge [graph.E-Edg];
        for(int j=0; j<graph.E; j++)
        {
            if(graph.edges[j].u!=i && graph.edges[j].v!=i)
            {
                new_graph->edges[x++]=graph.edges[j];
            }
            else Deleted_Edges[y++]=graph.edges[j];
        }
        current=Kruskal(new_graph);
        current+=two_minimum(Deleted_Edges, graph.E-Edg);
        if(current>lbound) lbound=current;
        delete[]new_graph->edges;
        delete[]Deleted_Edges;
        delete new_graph;
    }
    return lbound;
}