อาณาจักร ICPC มีทะเลสาบทรงกลมขนาดใหญ่อยู่ตรงกลาง และเมืองทุกเมืองพัฒนาขึ้นรอบทะเลสาบเป็นวงกลม เนื่องจากทุกเมืองพัฒนาตามผังเมืองเดียวกัน เมืองเหล่านี้จึงมีลักษณะคล้ายกันมาก โดยมีเครือข่ายรถไฟใต้ดินเหมือนกันทุกประการ บางสถานียังเป็นสถานีรถไฟความเร็วสูงระหว่างเมือง ซึ่งเชื่อมสถานีที่ตรงกันของเมืองที่อยู่ติดกันสองเมืองด้วย ทุกเส้นทางรถไฟให้บริการทั้งสองทิศทางระหว่างสถานีปลายทางสองแห่ง โดยไม่มีสถานีระหว่างทาง

ทุกเมืองมีจำนวนสถานีรถไฟใต้ดินและเส้นทางรถไฟใต้ดินเท่ากัน ในแต่ละเมือง สถานีมีหมายเลขเรียงกันเป็น $0,1,2,\ldots$ การที่สถานีสองแห่งในเมืองหนึ่งเชื่อมกันด้วยเส้นทางรถไฟใต้ดินหรือไม่นั้น ขึ้นอยู่กับหมายเลขสถานีเท่านั้น ไม่ขึ้นอยู่กับเมือง หากสถานี $v$ เชื่อมกับสถานี $u$ ในเมืองหนึ่ง ก็จะเชื่อมกันในเมืองอื่นทุกเมืองเช่นกัน ระยะทางเดินทางระหว่างสถานี $v$ และ $u$ เท่ากันในทุกเมือง

ทุกเมืองมีรายการหมายเลขสถานีรถไฟความเร็วสูงเหมือนกันทุกประการ หากสถานี $s$ เป็นสถานีรถไฟความเร็วสูงในเมืองหนึ่ง ก็จะเป็นเช่นนั้นในเมืองอื่นทุกเมืองเช่นกัน สถานีรถไฟความเร็วสูงที่มีหมายเลขเดียวกันในเมืองที่อยู่ติดกันสองเมืองทุกคู่เชื่อมกันด้วยเส้นทางรถไฟความเร็วสูง หากสถานี $s$ เป็นปลายทางด้านหนึ่งของเส้นทางรถไฟความเร็วสูง สถานี $s$ ในเมืองที่อยู่ติดกันจะเป็นปลายทางอีกด้านหนึ่ง ไม่มีเส้นทางรถไฟความเร็วสูงอื่นอีก เราสามารถเดินทางระหว่างสถานีสองแห่งใด ๆ ในอาณาจักรโดยใช้บริการรถไฟใต้ดินและ/หรือรถไฟความเร็วสูงอย่างน้อยหนึ่งเส้นทาง

เนื่องจากปัญหาทางการเงินในช่วงไม่กี่ปีที่ผ่านมา อาณาจักรจึงวางแผนยกเลิกบริการรถไฟใต้ดินและรถไฟความเร็วสูงบางเส้นทาง เพื่อลดค่าบำรุงรักษาระบบรถไฟ ค่าบำรุงรักษาคือผลรวมของค่าบำรุงรักษาเส้นทางรถไฟใต้ดินและเส้นทางรถไฟความเร็วสูง ค่าบำรุงรักษาเส้นทางรถไฟใต้ดินเป็นผลรวมของค่าใช้จ่ายพื้นฐานที่ขึ้นอยู่กับเมือง และค่าใช้จ่ายที่แปรผันตามระยะทางเดินทางของเส้นทางนั้น ค่าบำรุงรักษาเส้นทางรถไฟความเร็วสูงขึ้นอยู่กับเมืองสองเมืองที่เส้นทางนั้นเชื่อมต่อเท่านั้น

คุณต้องจัดทำแผนยกเลิกเส้นทางบางเส้นทาง เพื่อให้ค่าบำรุงรักษารวมต่ำที่สุด แน่นอนว่าหลังจากยกเลิกแล้ว สถานีทุกคู่ในอาณาจักรยังต้องเชื่อมถึงกันได้ด้วยบริการรถไฟใต้ดินและ/หรือรถไฟความเร็วสูงอย่างน้อยหนึ่งเส้นทาง

ข้อมูลนำเข้า

ข้อมูลนำเข้าประกอบด้วยกรณีทดสอบหนึ่งกรณีในรูปแบบต่อไปนี้

$$ \begin{gathered} n\quad m \\ v_1\quad u_1\quad d_1 \\ \vdots \\ v_m\quad u_m\quad d_m \\ l \\ a_0\quad b_0 \\ \vdots \\ a_{l-1}\quad b_{l-1} \\ r \\ s_1 \\ \vdots \\ s_r \end{gathered} $$

ในที่นี้ $n$ เป็นจำนวนเต็มที่ $2 \le n \le 10^4$ ซึ่งเป็นจำนวนสถานีรถไฟใต้ดินในหนึ่งเมือง สถานีในแต่ละเมืองมีหมายเลขตั้งแต่ $0$ ถึง $n-1$ ส่วน $m$ เป็นจำนวนเต็มที่ $1 \le m \le 10^5$ ซึ่งเป็นจำนวนเส้นทางรถไฟใต้ดินในหนึ่งเมือง ข้อมูล $m$ บรรทัดถัดไปอธิบายระบบรถไฟใต้ดินในหนึ่งเมือง บรรทัดที่ $i$ ใน $m$ บรรทัดนี้มีจำนวนเต็มสามจำนวน $v_i,u_i,d_i$ โดย $0 \le v_i < n$、$0 \le u_i < n$、$v_i \ne u_i$ และ $1 \le d_i \le 10^9$ หมายความว่ามีเส้นทางรถไฟใต้ดินเชื่อมสถานีหมายเลข $v_i$ และ $u_i$ และส่วนของค่าบำรุงรักษาที่แปรผันตามระยะทางเดินทางมีค่า $d_i$ ระหว่างสถานีสองแห่งใด ๆ มีเส้นทางรถไฟใต้ดินได้ไม่เกินหนึ่งเส้นทาง สถานีรถไฟใต้ดินทั้งหมดในเมืองเดียวกันเชื่อมถึงกันโดยตรงหรือโดยอ้อมผ่านเส้นทางรถไฟใต้ดินอย่างน้อยหนึ่งเส้นทาง

$l$ ในบรรทัดถัดไปเป็นจำนวนเต็มที่ $3 \le l \le 10^5$ ซึ่งเป็นจำนวนเมืองในอาณาจักร เมืองมีหมายเลขตั้งแต่ $0$ ถึง $l-1$ และเมือง $0$ เรียกอีกอย่างว่าเมือง $l$ สำหรับทุก $0 \le j \le l-1$ เมือง $j$ และเมือง $j+1$ อยู่ติดกัน $a_j$ และ $b_j$ ใน $l$ บรรทัดถัดไปเป็นจำนวนเต็มที่ $1 \le a_j \le 10^9$ และ $1 \le b_j \le 10^9$ โดย $a_j$ คือค่าบำรุงรักษาของเส้นทางรถไฟความเร็วสูงหนึ่งเส้นทางที่เชื่อมเมือง $j$ และ $j+1$ ส่วน $b_j$ คือค่าใช้จ่ายพื้นฐานของเส้นทางรถไฟใต้ดินในเมือง $j$

$r$ เป็นจำนวนเต็มที่ $1 \le r \le n$ ซึ่งเป็นจำนวนสถานีรถไฟความเร็วสูงในแต่ละเมือง $s_1,s_2,\ldots,s_r$ คือหมายเลขสถานีรถไฟความเร็วสูงในแต่ละเมือง

ข้อมูลส่งออก

พิมพ์จำนวนเต็มหนึ่งจำนวนในบรรทัดเดียว แทนค่าบำรุงรักษาระบบรถไฟที่ต่ำที่สุดหลังจากยกเลิกเส้นทาง โดยต้องทำให้ค่าใช้จ่ายต่ำที่สุดพร้อมทั้งรักษาให้สถานีทุกแห่งเชื่อมถึงกันโดยตรงหรือโดยอ้อม

ตัวอย่าง

ข้อมูลนำเข้า 1

2 1
0 1 3
3
6 1
4 2
5 3
1
1

ข้อมูลส่งออก 1

24

ข้อมูลนำเข้า 2

3 3
0 1 7
1 2 8
2 0 5
4
8 1
5 1
9 3
7 3
2
1
2

ข้อมูลส่งออก 2

76

ข้อมูลนำเข้า 3

5 8
0 1 1
2 1 2
4 0 5
3 4 7
3 2 8
0 2 4
4 1 3
2 4 6
6
3 2
9 3
7 1
5 3
3 2
5 2
4
0
2
3
4

ข้อมูลส่งออก 3

120