There is a new version of the Traveling salesman problem. 

Alice entered a country that contains n cities and she wants to see all of the cities by incurring the the minimum cost possible. There are m two-way roads in the country. A road connects two cities and it has a cost. The $i^{th}$ road connects cities $v_i,\ u_i$ and costs $c_i$. The difference between this problem and the classic TSP problem is that switching from a road to another road has a cost.

The viscosity for each road is defined as the $i^{th}$ road has viscosity $g_i$. Switching from a road with viscosity x to a road with viscosity y adds $\sqrt{x^2+y^2}$ cost.
Find the minimum cost needed to see all of the cities.

Note

• Alice is comfortable with seeing a city or a road several times.
• This problem is an approximation problem and you will get a higher score if you print a path with a lower cost.

Input format

• The first line contains two integers n, m.
• The next m lines contain the description of roads where the $i^{th}$ line contains $v_i,\ u_i,\ c_i,\ and\ g_i$.

Output format

Print the order in which Alice will see the cities. In the first line, print k that denotes the number of roads in her path ($n - 1 \le k \le 10^6$). In the next line, print the numbers of the roads she will pass in order.

Constraints

$3 \le n, m \le 10^5\\ 1 \le c_i, g_i \le 10^9$

Country is connected