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