27427번 - Lazy 스페셜 저지다국어

문제

Everybody knows that Romanian construction workers are very lazy. One of these workers is Dorel, who works for a company that builds roads across the country. Yesterday he received his new task: he is given N Romanian cities across the country (labeled from 1 to N), and M two-way roads (labeled from 1 to M) which are not yet built, each connecting exactly two cities; out of these roads he has to select and build N-1 so that all the cities become connected. Unfortunately the problem is not so simple for Dorel: each road i has two associated costs: C1_i - the effort to build the road and C2_i - the profit obtained per unit of effort spent for building the road. C1_i * C2_i is the profit of building the road. Of course Dorel wants to work as little as possible so the most important thing is that the effort of building all the roads must be minimum; if there are more ways of building roads so that the total effort is minimum, Dorel wants the total profit (the sum of profits for each road) to be maximum.

You have to solve Dorel's problem!

입력

On the first line of the standard input there are two numbers N and M, the number of cities and the number of roads. Next are M lines, the i-th of these lines has 4 natural numbers: a_i and b_i representing the cities road i connects, C1_i and C2_i.

출력

You must print to the standard output must contain N-1 lines representing the indexes (according to the input) of the roads which should be chosen by Dorel.

제한

• 1 ≤ N, M ≤ 200.000
• 1 ≤ a_i, b_i ≤ N
• 1 ≤ C1_i < 10¹⁷
• -10¹⁷ < C2_i < 10¹⁷
• if there are several solutions you can output anyone of them

힌트