Әсем кампуста Панда мен оның достары бірге тамақтану үшін кездеспекші. Олар жол-жөнекей бірге уақыт өткізгенді ұнатады, өйткені бір-бірімен еркін әңгімелесе алады.

Кампус ұзындықтары бар $m$ қырдан және $n$ төбеден тұратын байланысқан бағытталмаған граф ретінде модельденеді. Кездесу орны — $1$-ші төбеде орналасқан сауда орталығы. $k$ дос әртүрлі төбелерден шығып, сауда орталығына қарай жүреді. Барлық достар бірдей жылдамдықпен (уақыт бірлігінде $1$ қашықтық бірлігі) қозғалады және қырдың бойындағы кез келген нүктеде қозғалыс бағытын өзгерте алады (мысалдың түсіндірмесін қараңыз).

Барлық достар сауда орталығына жете алатын ең ерте мүмкін уақыт мезетін $t_{\text{meet}}$ деп белгілейік. Осы ең ерте мүмкін кездесу уақытына сүйене отырып, әрбір дос үшін жеке-жеке сауда орталығындағы соңғы жиналуға дейін серіктестікте (яғни графтағы дәл сол орында — төбеде немесе қырдың бойындағы нүктеде кемінде тағы бір басқа дос бірге болатын күйде) өткізе алатын ең көп жалпы уақытын табыңыз.

Нақты бір $i$ досын қарастырған кезде, барлық достар сауда орталығына $t_{\text{meet}}$ уақытынан кешікпей жету шарты орындалатындай етіп, барлық басқа $j \neq i$ достарының жолдары мен қозғалыс стратегиялары $i$ досының серіктестікте болу уақытын барынша арттыру үшін оңтайландырылады.

Кіріс деректері

Бірінші жолда тест жағдайларының санын білдіретін бүтін сан $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$ болатын қырды білдіретін үш бүтін сан $u, v, w$ ($1 \le u, v \le n$, $u \neq v$, $1 \le w \le 10^9$) берілген. Граф байланысқан және онда еселі қырлар немесе ілмектер жоқ.

Барлық тест жағдайлары бойынша $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.5$ уақыт бірлігі ішінде $(1, 2)$ қырының ортасында кездесіп, тағы $1.5$ бірлік ішінде сауда орталығына бірге қайтып оралып, содан кейін сауда орталығында $2$ бірлік күте алады, бұл барлығы $3.5$ бірлік серіктестік уақытын береді.
• $3$ төбесінен шыққан дос $2.5$ уақыт бірлігі ішінде $(1, 3)$ қырының ортасында $1$ төбесінен шыққан достармен кездесіп, олармен бірге $2.5$ бірлік ішінде қайтып оралады, бұл барлығы $2.5$ бірлік серіктестік уақытын береді.