20853번 - 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 $N$ olika platser, numrerade mellan 1ドル$ och $N,ドル med $M$ dubbelriktade vägar som var och en ansluter två olika platser. Han befann sig länge på en viss plats $X$ (det är okänt vilken), men sedan så flyttade han sig till en annan plats $Y$ (som vi inte heller känner till) genom att färdas längs en sekvens av vägar.

Polisen har samlat in $K$ 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$ på vägen från $X$ till $Y$ (det är även möjligt att $a_i = X$ eller $a_i = Y$ för något $i$). Däremot vet de inte i vilken ordning platserna besöktes. Waxel kan dessutom ha besökt fler än dessa $K$ platser på vägen från $X$ till $Y$.

Din uppgift är nu att hjälpa polisen att hitta de platser som möjligtvis kan vara $Y,ドル 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 $X$ till $Y$. 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, $N$ (2ドル \leq N \leq 2\cdot 10^5$),
• antalet vägar i staden, $M$ (1ドル \leq M \leq 2 \cdot 10^5$), och
• antalet vittnesmål, $K$ (1ドル \leq K \leq N$).

Den andra raden innehåller de $K$ olika heltalen $a_1, \dots, a_K$ (1ドル \leq a_i \leq N$), de platser som Waxel besökte.

De $M$ följande raderna beskriver de olika vägarna i staden. Den $i$:te raden innehåller de tre heltalen $u_i,ドル $v_i$ (1ドル \leq u_i \not= v_i \le N$) och $w_i$ (1ドル \leq w_i \leq 10^9$), vilket innebär att den $i$:te vägen förbinder platserna $u_i$ och $v_i$ och har längd $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 $Y$. Notera att detta tal kan vara 0ドル$.

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

제한

힌트

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

I exempel 2ドル$ finns det ingen kortaste väg som passerar de givna noderna. Svaret är alltså 0ドル$.

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