## Editorial for Xây dựng đường

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của ladpro98

program qbbuild;
uses    math;
const   oo=high(longint);
fi='';
maxn=105;
var     n,m,res:longint;
d:array[1..maxn,1..maxn] of longint;
s:array[1..4] of longint;

procedure input;
var     inp:text;
i,j,x,y,w:longint;
begin
assign(inp,fi);
reset(inp);
for i:=1 to n do
for j:=1 to n do
begin
if i=j then d[i,j]:=0
else    d[i,j]:=oo;
end;
while not eof(inp) do
begin
if d[x,y]>w then
begin
d[x,y]:=w;
d[y,x]:=w;
end;
end;
close(inp);
end;

procedure floyd;
var     i,j,k:longint;
begin
for k:=1 to n do
for i:=1 to n do
if d[i,k]<oo then
for j:=1 to n do
if d[k,j]<oo then
begin
if d[i,j]>d[i,k]+d[k,j] then
d[i,j]:=d[i,k]+d[k,j];
end;
end;

procedure output;
var     I,J,p,q,r,T,sum:longint;
begin
res:=oo;
for i:=1 to n do
for j:=i to n do
begin
for p:=1 to 4 do
for q:=1 to 4 do
for r:=1 to 4 do
for t:=1 to 4 do
if (p*q*r*t=24) and (p+q+r+t=10) then
res:=min(res,d[i,s[p]]+d[i,s[q]]+d[j,s[r]]+d[j,s[t]]+d[i,j]);
end;
write(res);
end;

begin
input;
floyd;
output;
end.


#### Code mẫu của RR

#include <iomanip>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

const double PI = acos(-1.0);

#define TWO(x) (1<<(x))
#define CONTAIN(S,x) (S & TWO(x))

int n, m, k;
int f[111][222], mark[111];
vector< pair<int,int> > ke[111];
set< pair<int, pair<int,int> > > s;

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
scanf("%d", &n); k = 4;

FOR(i,1,k) {
int u; scanf("%d", &u);
mark[u] = i;
f[u][TWO(i-1)] = 0;
s.insert(MP(0,MP(u,TWO(i-1))));
}
int u, v, c;
while (scanf("%d%d%d", &u, &v, &c) == 3) {
ke[u].PB(MP(v,c));
ke[v].PB(MP(u,c));
}
while (!s.empty()) {
int l = s.begin()->F;
pair<int,int> now = s.begin()->S;
int u = now.F, mask = now.S;

if (now.S == TWO(k) - 1) {
printf("%d\n", l);
return 0;
}
s.erase(s.begin());

//        cout << u << ' ' << mask << endl;
REP(i,ke[u].size()) {
int v = ke[u][i].F, c = ke[u][i].S;
int mask2 = now.S;
if (mark[v]) mask2 |= TWO(mark[v] - 1);

int cost = f[u][mask] + c;
if (f[v][mask2] > cost) {
}

int cost = f[u][mask] + f[v][mask3] + c;
if (f[v][mask3 | mask] > cost) {
}
}
}
}
return 0;
}


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#define max 101
#define maxEC 50000
#define maxC max*maxEC
long c[max][max],Trace[max][max],n,a[5],min=maxC;
void Enter()
{
long u,v,x;
scanf("%ld",&n);
for(long i=1;i<=4;i++)
scanf("%ld",&a[i]);
for(u=1;u<=n;u++)
for(v=1;v<=n;v++)
{
if(u==v) c[u][v]=0;
else c[u][v]=maxC;
}
while(scanf("%ld %ld %ld",&u,&v,&x)>0&&x>0)
{
if(c[u][v]>x)
{
c[u][v]=x;
c[v][u]=x;
}
}
}
void Floyd()
{
for(long u=1;u<=n;u++)
for(long v=1;v<=n;v++)
Trace[u][v]=v;
for(long k=1;k<=n;k++)
for(long u=1;u<=n;u++)
for(long v=1;v<=n;v++)
if(c[u][v]>c[u][k]+c[k][v])
{
c[u][v]=c[u][k]+c[k][v];
Trace[u][v]=Trace[u][k];
}
}
void xuli()
{
for(long i=1;i<=n;i++)
for(int j = 1;j<=n;j++)
{
long mini=c[a[1]][i]+c[a[2]][i]+c[i][j]+c[a[3]][j]+c[a[4]][j];
if(mini<min)
min=mini;
//printf("%ld ",mini);
}
for(long i=1;i<=n;i++)
for(int j = 1;j<=n;j++)
{
long mini=c[a[1]][i]+c[a[4]][i]+c[i][j]+c[a[3]][j]+c[a[2]][j];
if(mini<min)
min=mini;
//printf("%ld ",mini);
}
for(long i=1;i<=n;i++)
for(int j = 1;j<=n;j++)
{
long mini=c[a[1]][i]+c[a[3]][i]+c[i][j]+c[a[4]][j]+c[a[2]][j];
if(mini<min)
min=mini;
//printf("%ld ",mini);
}
printf("%ld",min);
}
main()
{
Enter();
Floyd();
xuli();
//getch();
}


#### Code mẫu của ll931110

{\$MODE DELPHI}
Program QBBUILD;
Const
input  = '';
output = '';
maxn = 100;
maxc = 100000000;
maxd = 4;
Var
c: array[1..maxn,1..maxn] of integer;
a: array[1..maxd] of integer;
n,res: integer;

Var
f: text;
i,j,k,u,v: integer;
Begin
Assign(f, input);
Reset(f);

For i:= 1 to n do
For j:= 1 to n do
if i = j then c[i,j]:= 0 else c[i,j]:= maxc;

Readln(f, a[1], a[2], a[3], a[4]);
While not Eof(f) do
Begin
Readln(f, u, v, k);
If c[u,v] > k then
Begin
c[u,v]:= k;
c[v,u]:= k;
End;
End;

Close(f);
End;

Procedure Floyd;
Var
u,v,k: integer;
Begin
For k:= 1 to n do
For u:= 1 to n do
For v:= 1 to n do
if c[u,v] > c[u,k] + c[k,v]
then c[u,v]:= c[u,k] + c[k,v];
End;

Procedure solve;
Var
f: text;
i,j,tmp: integer;
Begin
res:= maxc;
For i:= 1 to n do
For j:= 1 to n do
Begin
tmp:= c[i,a[1]] + c[i,a[2]] + c[j,a[3]] + c[j,a[4]];

If tmp > c[i,a[1]] + c[i,a[3]] + c[j,a[2]] + c[j,a[4]]
then tmp:= c[i,a[1]] + c[i,a[3]] + c[j,a[2]] + c[j,a[4]];

If tmp > c[i,a[1]] + c[i,a[4]] + c[j,a[2]] + c[j,a[3]]
then tmp:= c[i,a[1]] + c[i,a[4]] + c[j,a[2]] + c[j,a[3]];

tmp:= tmp + c[i,j];
If res > tmp then res:= tmp;
End;

Assign(f, output);
Rewrite(f);
Writeln(f, res);
Close(f);
End;

Begin
Floyd;
solve;
End.


#### Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int n;
int id[4];
int a[101][101];
int inf;

int main() {
scanf("%d", &n);
for(int i=0;i<4;++i) scanf("%d", &id[i]);
inf = 1000000000;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i!=j) a[i][j] = inf;
else a[i][j] = 0;
{
int u, v, c;
while(scanf("%d%d%d", &u, &v, &c)!=EOF) {
a[u][v] <?= c;
a[v][u] <?= c;
}
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
a[i][j] <?= a[i][k] + a[k][j];
int result = inf;
sort( id, id+4);
do {
for(int u=1;u<=n;++u)
for(int v=1;v<=n;++v)
result <?= a[u][id[0]] + a[u][id[1]] + a[v][id[2]] + a[v][id[3]] + a[u][v];
} while(next_permutation(id,id+4));
printf("%d\n", result);
return 0;
}