Given a connected undirected graph $G$ with positive edge weights, where node 1 and node $N$ are connected, you are asked to remove at most $K$ edges such that node 1 and node $N$ remain connected, and the shortest path between these two nodes is as long as possible.

Input

This is an "answer submission" problem. The input files shortest1.in through shortest10.in are already provided in the contestant's directory.

The first line of each input file shortest*.in contains three positive integers $N$, $M$, and $K$. $N$ is the number of nodes, and $M$ is the number of edges. Nodes are numbered from 1 to $N$, and edges are numbered from 1 to $M$. The following $M$ lines each contain three positive integers $u$, $v$, and $w$, representing an edge between node $u$ and node $v$ with weight $w$.

Output

The first line of the output file shortest*.out contains a non-negative integer $T$ ($T \le K$), representing the number of edges to be removed.

The next $T$ lines each contain an integer $x$ between 1 and $M$, representing the removal of the $x$-th edge from the input. You must ensure that these $T$ integers are distinct.

Examples

Input 1

3 3 1
1 2 1
2 3 1
1 3 1

Output 1

1
3

Note

In the example, the shortest path length from node 1 to node 3 is 1. After removing the third edge, the shortest path length becomes 2.

Subtasks

For each test case, there are four scoring parameters $s_1, s_2, s_3, s_4$. Let $ans$ be the shortest path length of your solution.

• If you do not provide an output, the output is invalid, or the shortest path does not exist, you receive 0 points.
• If the shortest path exists, you receive 1 point.
• If $ans \ge s_1$, you receive 3 points.
• If $ans \ge s_2$, you receive 5 points.
• If $ans \ge s_3$, you receive 8 points.
• If $ans = s_4$, you receive 10 points.
• If $ans > s_4$, you receive 12 points.

Your score for the test case is the highest score among all satisfied conditions.

Implementation Details

There is a program named checker in your directory that can be used to check your output. You can use the following command in the terminal to check your output:

./checker N

where $N$ is the test case number. For example, to test the 3rd test case, you can use:

./checker 3

This program will check if your output solution is valid. If the solution is valid, the program will also provide the length of the shortest path for that solution.

Note

Please keep the input files *.in and your output files *.out safe and back them up regularly to avoid accidental deletion.