في حرم جامعي جميل، يلتقي Panda وأصدقاؤه لتناول وجبة طعام. إنهم يستمتعون بقضاء الوقت معاً في الطريق، حيث يمكنهم الدردشة بحرية مع بعضهم البعض.

يُمثَّل الحرم الجامعي كبيان غير موجه ومتصل يتكون من $n$ عقدة و $m$ ضلعاً لها أطوال. نقطة الالتقاء هي المركز التجاري (المول)، والذي يقع عند العقدة $1$. ينطلق $k$ أصدقاء من عقد متباينة ويتجهون إلى المركز التجاري. يتحرك جميع الأصدقاء بنفس السرعة (مسافة $1$ وحدة لكل وحدة زمنية)، ويُسمح لهم بتغيير اتجاههم عند أي موضع على طول أي ضلع (انظر شرح المثال).

ليكن $t_{\text{meet}}$ أبكر وقت ممكن بحيث يتمكن جميع الأصدقاء من الوصول إلى المركز التجاري بحلول ذلك الوقت. بناءً على أبكر وقت التقاء ممكن هذا، لكل صديق على حدة، أوجد أقصى إجمالي وقت يمكنه قضاؤه برفقة آخرين (أي وجود صديق آخر واحد على الأقل في نفس الموقع تماماً على البيان، سواء كان عقدة أو موضعاً على طول ضلع) قبل التجمع النهائي في المركز التجاري.

عند دراسة صديق معين $i$، يتم تحسين مسارات واستراتيجيات حركة جميع الأصدقاء الآخرين $j \neq i$ لتعظيم وقت الرفقة للصديق $i$، طالما أن جميع الأصدقاء يصلون إلى المركز التجاري في موعد لا يتجاوز $t_{\text{meet}}$.

الإدخال

يحتوي السطر الأول على عدد صحيح $T$ ($1 \le T \le 10^4$)، يمثل عدد حالات الاختبار.

لكل حالة اختبار، يحتوي السطر الأول على ثلاثة أعداد صحيحة $n, m, k$ ($2 \le n \le 3 \times 10^5$, $n - 1 \le m \le 10^6$, $2 \le k \le n$)، تمثل عدد العقد والأضلاع والأصدقاء على الترتيب.

يحتوي السطر الثاني على $k$ أعداد صحيحة متباينة $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n$)، تشير إلى عقد البداية للأصدقاء.

تحتوي الأسطر الـ $m$ التالية في كل منها على ثلاثة أعداد صحيحة $u, v, w$ ($1 \le u, v \le n$, $u \neq v$, $1 \le w \le 10^9$)، تشير إلى وجود ضلع بين العقدة $u$ والعقدة $v$ بطول $w$. البيان متصل ولا يحتوي على أضلاع مكررة أو حلقات ذاتية.

مجموع $n$ عبر جميع حالات الاختبار لا يتجاوز $3 \times 10^5$، ومجموع $m$ عبر جميع حالات الاختبار لا يتجاوز $10^6$.

الإخراج

لكل حالة اختبار، اطبع سطراً يحتوي على $k$ أعداد عشرية مفصولة بمسافات، كل منها مُنسَّق إلى منزلة عشرية واحدة بالضبط، تمثل أقصى وقت برفقة الأصدقاء لكل صديق.

أمثلة

الإدخال 1

3
4 3 2
3 4
1 2 3
3 2 1
4 2 1
2 1 2
1 2
1 2 3
3 2 3
1 2 3
1 2 3
1 3 5

الإخراج 1

3.0 3.0
1.5 1.5
3.5 3.5 2.5

ملاحظة

بالنسبة لحالة الاختبار الثالثة في المثال، فإن أبكر وقت للالتقاء في المركز التجاري هو $5$ وحدات زمنية.

• يمكن للصديقين المنطلقين من العقدتين $1$ و $2$ الالتقاء في منتصف الضلع $(1, 2)$ خلال $1.5$ وحدة زمنية، والعودة معاً إلى المركز التجاري خلال $1.5$ وحدة أخرى، ثم الانتظار لمدة $2$ وحدة في المركز التجاري، ليصبح المجموع $3.5$ وحدة من الرفقة.
• يلتقي الصديق المنطلق من العقدة $3$ بالأصدقاء المنطلقين من العقدة $1$ في منتصف الضلع $(1, 3)$ خلال $2.5$ وحدة زمنية ويعود معهم خلال $2.5$ وحدة، ليصبح المجموع $2.5$ وحدة من الرفقة.