توجد في وسط مملكة ICPC بحيرة كبيرة مستديرة، وقد بُنيت جميع مدنها حول البحيرة لتشكّل حلقة من المدن. ولأنها جميعًا طُوّرت وفق المخطط العمراني نفسه، فإن المدن متشابهة جدًا، ولديها شبكات مترو متطابقة تمامًا. بعض محطاتها هي أيضًا محطات قطارات فائقة السرعة بين المدن، تصل بين محطتين متناظرتين في مدينتين متجاورتين. تتيح جميع خطوط القطارات الحركة في الاتجاهين بين محطتي النهاية، دون محطات وسيطة.

تحتوي المدن على العدد نفسه من محطات المترو وخطوطه. في كل مدينة، تُرقّم المحطات بالتتابع $0,1,2,\ldots$. يعتمد اتصال محطتين داخل المدينة بخط مترو على رقمي المحطتين فقط، وليس على المدينة. فإذا كانت المحطة $v$ متصلة بالمحطة $u$ في مدينة، فإن الأمر نفسه ينطبق في جميع المدن الأخرى. ومسافة السفر بين المحطتين $v$ و$u$ متساوية في جميع المدن.

لدى جميع المدن قائمة متطابقة تمامًا بأرقام محطات القطارات فائقة السرعة. إذا كانت المحطة $s$ محطة قطار فائق السرعة في مدينة، فهي كذلك في جميع المدن الأخرى. كل زوج من محطتي قطار فائق السرعة لهما الرقم نفسه في مدينتين متجاورتين متصل بخط قطار فائق السرعة. إذا كانت المحطة $s$ أحد طرفي خط كهذا، فإن المحطة $s$ في المدينة المجاورة هي طرفه الآخر. ولا توجد خطوط قطارات فائقة السرعة أخرى. يمكن السفر بين أي محطتين في المملكة باستخدام خدمة مترو و/أو قطار فائق السرعة واحدة أو أكثر.

بسبب الصعوبات المالية في السنوات الأخيرة، تخطط المملكة لإيقاف بعض خدمات المترو والقطارات فائقة السرعة لتقليل تكلفة صيانة شبكة السكك الحديدية. تكلفة الصيانة هي مجموع تكاليف صيانة خطوط المترو وخطوط القطارات فائقة السرعة. تكلفة صيانة خط مترو هي مجموع تكلفة أساسية تعتمد على المدينة وتكلفة تتناسب مع مسافة السفر على الخط. أما تكلفة صيانة خط قطار فائق السرعة فتعتمد فقط على المدينتين اللتين يصلهما.

مطلوب منك وضع خطة لإيقاف بعض الخطوط بحيث تكون تكلفة الصيانة الإجمالية أقل ما يمكن. وبالطبع يجب أن يبقى كل زوج من محطات المملكة متصلًا بواسطة خدمة مترو و/أو قطار فائق السرعة واحدة أو أكثر بعد الإيقاف.

الإدخال

يتكون الإدخال من حالة اختبار واحدة بالتنسيق التالي:

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

هنا $n$ عدد صحيح يحقق $2\le n\le 10^4$، وهو عدد محطات المترو في كل مدينة. تُرقّم محطات كل مدينة من $0$ إلى $n-1$. و$m$ عدد صحيح يحقق $1\le m\le 10^5$، وهو عدد خطوط المترو في كل مدينة. تصف الأسطر $m$ التالية نظام المترو في مدينة. يحتوي السطر $i$ منها على ثلاثة أعداد صحيحة $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