== include(page="template/taskheader" task_id="tempest") ==

Poveste şi cerinţă...

Fie un graf cu $N$ noduri si $M$ muchii bidirectionale. Pentru fiecare muchie se cunoaste timpui necesar pentru a parcurge muchia respectiva. Yoshino se afla in nodul $S$(sursa) si parcurge un drum DAT pana in $D$(destinatie). Hakaze stie ca Yoshino cand o sa ajunga in nodul $D$, secunda imediat urmatoare acesta o sa moara. Ca urmare Hakaze trebuie sa il gaseasca pe Yoshino inainte ca acesta sa ajunga in destinatie (sau sa se intalneasca fix in destinatie). Hakaze este curioasa din cate noduri poate pleca astfel incat sa se poata intalni cu Yoshino inainte ca acesta sa moara (cei doi se pot intalni ori intr-un nod, ori pe o muchie).

h2. Date de intrare

Fişierul de intrare $tempest.in$ ...

Fişierul de intrare $tempest.in$ va contine pe prima linie un numar $T$, numarul de teste. Pentru fiecare test o sa avem: pe prima linie avem $N$, $M$, $S$ si $D$. Pe urmatoarele $M$ linii se vor afla cate $3$ numere $x$ $y$ $time$, reprezentand ca exista muchie bidirectionala de la $x$ la $y$ care este parcursa in time unitati de timp. Urmatoarea linie contine un numar $K$ (numarul de muchii parcurse de Yoshino). Pe ultima linie vor fi $K$ numere, indicii muchiilor.
 

h2. Date de ieşire

În fişierul de ieşire $tempest.out$ ...

Fişierul de ieşire $tempest.out$ va contine pentru fiecare din cele $T$ teste cate $2$ linii. Pe prima linie $R$, numarul de noduri din care poate sa plece Hakaze. Pe cea de a doua linie indicii celor $R$ noduri.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 300.000$
* Costurile muchiilor vor fi in intervalul $[1, 1.000.000.000]$
* Cele $K$ noduri trebuie afisate in ordine crescatoare

h2. Exemplu
table(example). |_. tempest.in |_. tempest.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|1
5 8 1 2
1 2 5
2 3 3
1 3 4
1 4 1
4 5 2
1 5 6
2 5 10
3 5 7
2
3 2
|4
1 2 3 4

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="tempest") ==