בקמפוס יפהפה, 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$ יחידות של שהות משותפת.