Note: This is an approximate problem. No exact solution exists for this question. You must find the most optimal solution. Refer to the sample explanation to ensure that you understand the problem correctly.
 

Problem statement

You are given a weighted connected graph $G$ with $N$ vertices and $M$ edges. There are no self-loops and multiple edges between two vertices in $G$. You are given two vertices $u$ and $v\ (u != v)$. Here, $u$ is the Source and $v$ is the Destination. Also, you are given a set of $K$ vertices $B_1,\ B_2,\ ...,\ B_k$ (no vertex is equal to $u$ and $v$). Your task is to find a path between source and destination such that value of $Z$ is minimized.

$Z = Weight\ of\ path \times Y$.

where $Y$ is equal to the count of the vertex on a path that does not belong to a set of $K$ vertices.

Input format

• The first line contains three space-separated integers $N\ M\ K$.
• The next line contains two integers $u$ and $v$ denoting the source and destination vertex.
• Each of the next $M$ lines contains 3 space-separated integers $u\ v\ w$ denoting edge between vertex $u$ and $v\ (u != v)$ with weight $w$ ($\le 1e5$).
• The next line contains $K$ space-separated integers denoting the vertices $B_1,\ B_2,\ ...,\ B_k$.

Output format

$X\ (X < N )$ is the length of the path that you can find. The format of the output is as follows:

• In the first line, print $X$ denoting the length of the path (number of edges in the path)
• In each of the $X$ lines, print the edge numbers (position of the edge in the Input) in a sequential form.
  For example 
  If the path found is $a_1,\ a_2,\ a_3,\ ...,\ a_p$, then print $X = P - 1$ (length of the path), $Source\ =\ a_1,\ and\ Destination\ =\ a_p$.
  Edge number for edge connecting $a_1\ a_2$
  Edge number for edge connecting $a_2\ a_3$
  Edge number for edge connecting $a_3\ a_4$
  ...............
  Edge number for edge connecting $a_{p-1}\ a_p$

Constraints

$2 ≤ N ≤ 10000,\ N - 1 \le M \le 100000,\ 1 \le K \le 5000\\ 1 \le w \le 1e5,\ 1 \le u,v \le N,\ 1 \le B_i \le N,\ All\ B_i\ are\ distinct$

Verdict and scoring

Your score is equal to the sum of the values of all test files. The value of each test file is equal to the value of $Z$ that you can find.

If the path is invalid, then you receive Wrong Answer Verdict.

Test generation plan

In 20% tests: ($1≤N≤1000,\ 1 \le K\le 500$) 

In 80% tests: ($1≤N≤10000,\ 1 \le K \le 5000$) 

The input is randomly generated for each test file.