Efterlyst

문제

Poliskonstapel Acsel behöver din hjälp med ett brådskande ärende, nämligen att fånga den farliga brottsligen Waxel. Waxel gömmer sig någonstans i en stad som består av $NN$ olika platser, numrerade mellan $11$ och $NN$, med $MM$ dubbelriktade vägar som var och en ansluter två olika platser. Han befann sig länge på en viss plats $XX$ (det är okänt vilken), men sedan så flyttade han sig till en annan plats $YY$ (som vi inte heller känner till) genom att färdas längs en sekvens av vägar.

Polisen har samlat in $KK$ stycken vittnesmål från personer som såg Waxel. Därför vet de att Waxel besökte platserna $a_1,a_2,\dots ,a_{K}a\_1,\; a\_2,\; \backslash dots,\; a\_K$ på vägen från $XX$ till $YY$ (det är även möjligt att $a_i=Xa\_i\; =\; X$ eller $a_i=Ya\_i\; =\; Y$ för något $ii$). Däremot vet de inte i vilken ordning platserna besöktes. Waxel kan dessutom ha besökt fler än dessa $KK$ platser på vägen från $XX$ till $YY$.

Din uppgift är nu att hjälpa polisen att hitta de platser som möjligtvis kan vara $YY$, under förutsättning att Waxel tog en kortaste sekvens av vägar (Detta innebär att summan av längderna av de vägar som Waxel färdades längs är så liten som möjligt.) från $XX$ till $YY$. Det är möjligt att det inte finns några sådana platser alls, om vittnesmålen inte stämmer överens med någon kortaste väg.

입력

Den första raden innehåller tre heltal:

• antalet platser i staden, $NN$ ($2\le N\le 2\cdot {10}^{5}2\; \backslash leq\; N\; \backslash leq\; 2\backslash cdot\; 10^5$),
• antalet vägar i staden, $MM$ ($1\le M\le 2\cdot {10}^{5}1\; \backslash leq\; M\; \backslash leq\; 2\; \backslash cdot\; 10^5$), och
• antalet vittnesmål, $KK$ ($1\le K\le N1\; \backslash leq\; K\; \backslash leq\; N$).

Den andra raden innehåller de $KK$ olika heltalen $a_1,\dots ,a_{K}a\_1,\; \backslash dots,\; a\_K$ ($1\le a_i\le N1\; \backslash leq\; a\_i\; \backslash leq\; N$), de platser som Waxel besökte.

De $MM$ följande raderna beskriver de olika vägarna i staden. Den $ii$:te raden innehåller de tre heltalen $u_{i}u\_i$, $v_{i}v\_i$ ($1\le u_i≠v_i\le N1\; \backslash leq\; u\_i\; \backslash not=\; v\_i\; \backslash le\; N$) och $w_{i}w\_i$ ($1\le w_i\le {10}^{9}1\; \backslash leq\; w\_i\; \backslash leq\; 10^9$), vilket innebär att den $ii$:te vägen förbinder platserna $u_{i}u\_i$ och $v_{i}v\_i$ och har längd $w_{i}w\_i$ meter. Det är garanterat att det går att ta sig mellan vilka två platser som helst genom att färdas längs en sekvens av vägar och att det mellan varje par av platser finns högst en väg som förbinder platserna.

출력

På den första raden ska du skriva ut antalet noder som kan vara $YY$. Notera att detta tal kan vara $00$.

På den andra raden ska du skriva ut samtliga noder som kan vara $YY$. Dessa ska skrivas ut separerade av blanksteg i ökande ordning.

힌트

I exempel $11$ är platserna $1,2,4,51,2,4,5$ möjliga mål för Waxel. För att komma till $22$ hade han kunnat ta vägen $5-6-1-25-6-1-2$.

I exempel $22$ finns det ingen kortaste väg som passerar de givna noderna. Svaret är alltså $00$.

I exempel $33$ finns det ganska många möjligheter. För att komma till $22$ hade Waxel t.ex. kunnat ta vägen $6-7-5-3-1-26-7-5-3-1-2$.

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

4
1 2 4 5

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

0

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

5
1 2 5 6 7

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

4
2 3 4 5