program day3_3;
 const
   maxn=100;
 var
     n,m:           longint;
     ans,tot:       longint;
     g: array[0..maxn,0..maxn] of longint;
     c: array[1..maxn] of longint;


 procedure Init;
   var
       i,j,x,y:     longint;
   begin
     readln(n);
     fillchar(g,sizeof(g),$FF);
     for i :=1 to n do begin
         readln(c[i],x,y);
         g[i,x] :=1; g[x,i]:=1;
         g[i,y] :=1; g[y,i]:=1;
         end;
     for i :=1 to n do g[i,i] :=0;
   end;

 procedure Main;
   var
       k,i,j:     longint;
   begin
     for k :=1 to n do
       for i :=1 to n do
         for j :=1 to n do begin
         if  (k=i) or (k=j) or (i=j) then continue;
         if  (g[i,k]<>-1) and (g[k,j]<>-1) then
             if (g[i,j]=-1) or (g[i,k]+g[k,j]<g[i,j]) then
             g[i,j] :=g[i,k]+g[k,j];
             end;
     ans :=maxlongint;
     for i :=1 to n do begin
         tot :=0;
         for j :=1 to n do inc(tot,g[i,j]*c[j]);
         if tot < ans then ans :=tot;
         end;
     writeln(ans);
   end;

 begin
   assign(input,'hospital.in'); reset(input);
   assign(output,'hospital.out'); rewrite(output);
   Init;
   Main;
   close(input); close(output);
 end.