지하철 노선도

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

요약

일부 간선의 가중치가 알려지지 않은 연결 그래프에서, 표시된 간선들이 최소 신장 트리를 이루도록 각 미지 간선의 최소 가중치를 구한다.

난이도: 어려움10점 중 8점
유형: 최소 신장 트리, 유니온 파인드, 그래프, 그리디
정답자: 아직 제출이 없습니다

문제

2120년, 룬드 전체 지하에는 $N$ 개의 역과 $M$ 개의 터널로 이루어진 거대한 지하철망이 있다. 각 터널은 두 역을 연결하며, 역에는 $1$ , $\ldots$ , $N$ 의 번호가 붙어 있다.

Erik은 Skånetrafiken의 형편없는 경로 계획 소프트웨어에 지쳐 직접 만들기로 했다. 그러려면 각 터널의 길이를 알아야 하지만, 지하철 노선도에는 그 정보가 빠져 있다. 창밖을 보던 Erik은 일부 터널을 따라 특수한 케이블이 놓여 있는 것을 발견했다. 아마 역에 전력을 공급하기 위한 것일 것이다. 케이블은 모든 역이 중앙역(번호가 $1$ 인 역)과 연결되도록 배치되어 있다. Skånetrafiken이 얼마나 탐욕스러운지 아는 Erik은 케이블의 총 길이가 최소가 되도록 케이블이 놓였다고 확신한다.

Erik은 일부 터널의 정확한 길이와 어떤 터널에 케이블이 있는지를 알고 있다. 이 정보를 이용해 그는 길이를 모르는 각 터널의 가능한 최소 길이를 구하려 한다. 안타깝게도 Erik의 알고리즘은 룬드 지하철망의 거대한 크기를 처리하기에 충분히 효율적이지 않다. 더 효율적인 알고리즘을 구현해 그를 도와줄 수 있는가?

입력

첫째 줄에 두 정수 $N$ 과 $M$ 이 주어진다. $2 \leq N \leq 10^5$ 이고 $N - 1 \leq M \leq 2 \cdot 10^5$ 이며, 각각 역의 수와 터널의 수다. 다음 $M$ 개의 줄에는 $a_i$ , $b_i$ , $l_i$ , $c_i$ 가 주어진다. 정수 $a_i$ 와 $b_i$ 는 $1 \leq a_i, b_i \leq N$ 이고 $a_i\neq b_i$ 이며, $i$ 번째 터널이 연결하는 두 역을 나타낸다. $l_i$ 는 $i$ 번째 터널의 길이를 아는 경우 $1 \leq l_i \leq 10^9$ 를 만족하는 정수이고, 모르는 경우 물음표 “?”이다. 마지막으로 $c_i$ 는 $i$ 번째 터널에 케이블이 있으면 $1$ , 없으면 $0$ 이다.

같은 두 역을 연결하는 터널은 많아야 하나이고, 지하철을 이용해 임의의 두 역 사이를 이동할 수 있다. 또한 $c_i = 1$ 인 터널만 이용해 임의의 역과 $1$ 번 역 사이를 이동할 수 있다.

출력

$l_i=`?`$ 인 각 터널에 대해, 그 터널의 가능한 최소 길이를 나타내는 정수를 한 줄에 하나씩 출력한다. 터널의 길이는 입력에 주어진 순서대로 출력해야 한다.

힌트

첫 번째 예제에서 길이를 모르는 터널(역 $3$ 과 $1$ 사이)의 최소 길이는 $5$ 다. 길이가 $5$ 보다 작다면 Skånetrafiken은 두 번째와 세 번째 터널에 케이블을 놓는 편이 더 효율적이기 때문이다.

예제2

예제 1
입력
```
3 3
1 2 5 1
2 3 3 1
3 1 ? 0
```
예상 출력
```
5
```
예제 2
입력
```
4 3
1 2 ? 1
1 3 ? 1
2 4 ? 1
```
예상 출력
```
1
1
1
```