게으른 도로 건설

면접 대비

시간 제한1초메모리 제한1024 MB

요약

N개의 도시를 모두 잇는 N-1개의 도로를 고르되, C1 합을 최소로 하고 그다음 C1과 C2 곱의 합을 최대로 합니다.

난이도: 보통10점 중 5점
유형: 최소 신장 트리, 유니온 파인드, 정렬, 그리디
정답자: 아직 제출이 없습니다

문제

루마니아 건설 노동자들이 매우 게으르다는 것은 누구나 안다. 도렐도 그중 한 명이다. 그는 전국에 도로를 놓는 회사에서 일하며, 어제 새 업무를 받았다.

아직 건설되지 않은 루마니아 도시 $N$ 개(1부터 $N$ 까지 번호가 붙어 있다)와 양방향 도로 $M$ 개(1부터 $M$ 까지 번호가 붙어 있다)가 주어진다. 각 도로는 도시 두 개를 정확히 잇는다. 도렐은 이 도로들 가운데 $N-1$ 개를 골라 모든 도시가 연결되도록 건설해야 한다.

도로 $i$ 에는 비용이 두 개 있다. $C1_i$ 는 건설에 드는 노력이고, $C2_i$ 는 노력 한 단위당 얻는 이익이다. 도로 $i$ 를 건설해서 얻는 이익은 $C1_i \times C2_i$ 이다. 도렐은 최대한 적게 일하고 싶어 하므로, 먼저 건설하는 도로들의 노력 합이 최소여야 한다. 노력 합이 최소인 선택이 여럿이면, 이익 합(건설하는 도로 이익의 총합)이 최대인 선택을 택한다.

입력

첫 줄에 $N$ 과 $M$ 이 주어진다. 이어지는 $M$ 개의 줄에는 자연수 네 개 $a_i$ , $b_i$ , $C1_i$ , $C2_i$ 가 주어진다. 앞의 두 수는 도로 $i$ 가 잇는 두 도시이고, 뒤의 두 수는 그 도로의 비용이다.

출력

도렐이 건설해야 하는 도로의 번호(입력 순서 기준)를 $N-1$ 개의 줄에 한 줄씩 출력한다.

제한

$1 \le N, M \le 200{,}000$
$1 \le a_i, b_i \le N$
$1 \le C1_i < 10^{17}$
$-10^{17} < C2_i < 10^{17}$
여러 해가 있으면 그중 아무거나 출력해도 된다.

예제1

예제 1
입력
```
3 3
1 2 1 7
2 3 3 2
1 3 2 3
```
예상 출력
```
1
3
```