ZIM

#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

class droga
{public:
    int dokad;
    int koszt; //podzielność kosztu na 2, liczymy nadmiarowe przebiegi.
    droga(int d,int k){dokad=d; koszt=k%2;  }
};

class skrzyzowanie
{public:
    int mk0;
    int mk1;
    int mk2; //minmalny koszt dodatkowy dla 0, 1 i 2 wchodzących konców
    vector <droga> krawedzie;
};


void przetwarzaj ( vector<skrzyzowanie>&skrz, int ojc, int w )
{
    int krawedzi=skrz[w].krawedzie.size();

    if ((krawedzi==1)&&(skrz[w].krawedzie[0].dokad==ojc))
    {
        skrz[w].mk0=0;
        skrz[w].mk1=0;
        skrz[w].mk2=0;
    }else
    {
        int sum0=0;
        int min1a=0; // moze sie oplacać zrobic koncowkę w tym miejscu.
        int min1b=0;
        int min2 =0;

        for (int i=0; i<krawedzi; i++)
        {
            int dziecko = skrz[w].krawedzie[i].dokad;
            if ( dziecko != ojc)
            {
                przetwarzaj ( skrz, w, dziecko );

                int koszt_drogi = skrz[w].krawedzie[i].koszt;
                int koszt =skrz[dziecko].mk0 + koszt_drogi;

                int poprawka1 = skrz[dziecko].mk1 + (1-koszt_drogi) - koszt;
                //ile się poprawi, gdy w dziecko wpuścimy jedną koncówkę.
                int poprawka2 = skrz[dziecko].mk2 + (koszt_drogi) - koszt;
                //ile się poprawi, gdy w dziecko wpuścimy dwie koncówki.

                sum0 += koszt;
                if (min2>poprawka2)  min2 = poprawka2;
                if (min1b>poprawka1) min1b=poprawka1;
                if (min1a>min1b) swap(min1a,min1b);
            }
        }
        skrz[w].mk0=sum0;
        skrz[w].mk1=sum0 + min1a;
        skrz[w].mk2=sum0 + min( min1a+min1b, min2 );


    }//end nietrywialne kwawedzie

}

int main()
{
    int n;
    long long int koszt_konieczny=0;
    scanf("%d",&n);

    vector<skrzyzowanie>skrz(1+n);

    for (int i=0;i<n-1;i++)
    {
        int a, b, d;
        scanf ("%d %d %d",&a, &b, &d);
        skrz[a].krawedzie.push_back(droga(b,d));
        skrz[b].krawedzie.push_back(droga(a,d));
        koszt_konieczny+=d;
    }

    przetwarzaj(skrz,0,1);

    printf("%lld", koszt_konieczny + min(min(skrz[1].mk0,skrz[1].mk1),skrz[1].mk2));

    return 0;
}