#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
#define inf 1000000000
int dist[100];
bool verificare_minim_util(int a, int nr_detinuti, int locatii_detinuti[])
{
int i;
for (i=1;i<=nr_detinuti;i++)
if (a==locatii_detinuti[i])
return true;
return false;
}
int my_minimul(int ok[], int nr_noduri)
{
int i,my_min;
my_min=inf;
for (i=1;i<=nr_noduri;i++)
if ((ok[i]<my_min)&&(ok[i]!=-1))
my_min=ok[i];
return my_min;
}
int poz_my_min(int ok[], int nr_noduri, int my_min)
{
int i,poz;
for (i=1;i<=nr_noduri;i++)
if (ok[i]==my_min)
{
poz=i;
break;
}
return poz;
}
void dijkstra (vector <int> vec[],vector <int> cost[], int start, int nr_noduri,
vector <int> max_detinuti_per_muchie[], int nr_detinuti_curenti)
{
int ok[nr_noduri+1],i,j,k,my_min;
for (i=1;i<=nr_noduri;i++)
if (i==start)
{
dist[i]=0;
ok[i]=0;
}
else
{
dist[i]=inf;
ok[i]=inf;
}
k=0;
while (k<nr_noduri)
{
my_min=my_minimul(ok,nr_noduri);
i=poz_my_min(ok,nr_noduri,my_min);
ok[i]=-1;
for (j=0;j<vec[i].size();j++)
{
if ((cost[i][j]+my_min<dist[vec[i][j]])&&(nr_detinuti_curenti<=max_detinuti_per_muchie[i][j]))
{
dist[vec[i][j]]=cost[i][j]+my_min;
ok[vec[i][j]]=cost[i][j]+my_min;
}
}
k=k+1;
}
}
int main()
{
int nr_detinuti,nr_noduri,nr_muchii,i,j,a,b,c,d,nr_detinuti_curenti=0,min_d,q,poz,suma=0;
ifstream f("gather.in");
ofstream g("gather.out");
f>>nr_detinuti>>nr_noduri>>nr_muchii;
vector <int> vec[nr_noduri+1],cost[nr_noduri+1],max_detinuti_per_muchie[nr_noduri+1];
int locatii_detinuti[nr_noduri+1];
for (i=1;i<=nr_detinuti;i++)
f>>locatii_detinuti[i];
for (i=1;i<=nr_muchii;i++)
{
f>>a>>b>>c>>d;
vec[a].push_back(b);
vec[b].push_back(a);
cost[a].push_back(c);
cost[b].push_back(c);
max_detinuti_per_muchie[a].push_back(d);
max_detinuti_per_muchie[b].push_back(d);
}
for (i=1;i<=nr_detinuti;i++)
{
if (nr_detinuti_curenti==0)
{
dijkstra(vec,cost,1,nr_noduri,max_detinuti_per_muchie,nr_detinuti_curenti);
}
else
{
dijkstra(vec,cost,poz,nr_noduri,max_detinuti_per_muchie,nr_detinuti_curenti);
for (q=poz+1;q<=nr_detinuti;q++)
locatii_detinuti[q-1]=locatii_detinuti[q];
nr_detinuti=nr_detinuti-1;
}
min_d=inf;
for (j=1;j<=nr_noduri;j++)
if ((verificare_minim_util(j,nr_detinuti,locatii_detinuti)==true)&&(dist[j]<min_d)&&(dist[j]!=0))
{
min_d=dist[j];
poz=j;
}
if (nr_detinuti_curenti==0)
suma=min_d;
else
suma=suma+((nr_detinuti_curenti+1)*min_d);
nr_detinuti_curenti++;
}
g<<suma;
return 0;
}