Dima and the Famous Tourist#2931
The renowned tourist Gennady always chooses the shortest routes in his travels. A boy named Dima is an admirer of Gennady and collects every piece of information he can find about him—be it newspaper clippings, online news, and so on.
Recently, Gennady went on a journey. Along the way, some of his fans saw him in certain cities and wrote about it in their blogs. Dima found all these accounts, but since he conducted his search after the journey had ended, he could not restore the chronological order of the records—he only knows the set of cities that Gennady definitely visited. He knows for sure that Gennady traveled from one city to another by the shortest route. Help Dima reconstruct one possible route Gennady might have taken.
Dima uses only verified sources, so the existence of a path is guaranteed.
The first line contains and (1 \leq n, m \leq 10^5) — the number of cities and the number of roads, respectively. Each of the next lines contains a description of a road: a_i, b_i, t_i (a_i \neq b_i, 1 \leq a_i, b_i \leq n, 1 \leq t_i \leq 10^4) — the cities at the ends of the road and the travel time along it. The next line contains — the number of cities that Gennady definitely visited. The last line contains numbers — the identifiers of these cities. Each city in this list appears at most once.
Output the number of roads Gennady traveled on in the first line, and in the second line output these roads in the order Gennady visited them. If there are several possible solutions, output any of them.
Example 1