문제

서현 국가는 $N$개의 섬 도시와 $M$개의 양방향 다리로 이루어져 있으며, 모든 섬 도시는 다리를 통해 직간접적으로 연결되어 있다. 각 섬은 $1$부터 $N$까지 번호가 매겨져 있고, 각 다리는 $1$부터 $M$까지 번호가 매겨져 있다. $i(1\le i \le M)$번 다리는 섬 도시 $u_i$와 $v_i$를 연결하며, 초기에는 최대 $w_i$의 하중을 견딜 수 있다.

다리 강화 작업에 사용할 수 있는 예산 $B$가 주어진다. 각 다리는 한 번의 강화 작업을 통해 하중을 $x_i$만큼 증가시킬 수 있고, $y_i$만큼의 비용이 든다. 다리 강화 작업은 예산을 초과하지 않는 선에서 얼마든지 반복할 수 있고, 다리를 강화하지 않을 수도 있다.

강화 작업이 완료된 이후, 임의의 서로 다른 두 섬 $u$, $v$ 사이에서 물건을 배송한다고 생각해 보자. 두 섬을 연결하는 경로상의 다리 중 가장 하중이 낮은 다리의 하중이 배송 상한선이 된다. 가능한 경로가 여러 개라면 배송 상한선이 더 큰 경로를 선택한다. 그때의 배송 상한선을 $f(u, v)$라고 하자.

모든 서로 다른 두 섬 쌍 $(u, v)$에 대해서 $f(u, v)$의 최솟값을 $X$라 하자. 시민들의 불만을 줄이고자 $X$를 가능한 한 크게 하고 싶다. 그러기 위해서는 각 다리에 몇 번의 강화 작업을 수행해야 할까?

입력

첫째 줄에 $N$, $M$, $B$가 공백으로 구분되어 주어진다. $(2 ≤ N ≤ 50\,000;\; N - 1 ≤ M ≤ 100\,000;\; 1 ≤ B ≤ 1\,000\,000)$

둘째 줄부터 $M$개의 줄에 걸쳐, $i$번 다리의 정보 $u_i$, $v_i$, $w_i$, $x_i$, $y_i$가 공백으로 구분되어 주어진다. $(1 \le u_i, v_i \le N,\; u_i \neq v_i;\; 1 ≤ w_i, x_i ≤ 100\,000; 1\le y_i \le 10)$

입력으로 주어지는 수는 모두 정수이다.

출력

첫째 줄에 $X$의 최댓값을 출력한다.

둘째 줄부터 $M$개의 줄에 걸쳐, $i+1$번째 줄에 $i$번 다리를 몇 번 강화해야 하는지 출력한다. 정답이 여러 개라면 그중 하나만 출력한다.

예제 입력 1

3 3 1
1 2 5 1 1
2 3 1 4 1
1 3 3 1 1

예제 출력 1

5
0
1
0

강화 이전의 $f(1,2) =5$, $f(2,3) =3$, $f(1,3) =3$이므로 $X$는 $3$이다.

$2$번째 다리를 $1$회 강화하면 $X$는 $5$가 된다. 예산 내에서 $X$를 이보다 크게 만드는 경우는 존재하지 않는다.

예제 입력 2

3 3 1
1 2 5 1 1
2 3 1 4 2
1 3 3 1 1

예제 출력 2

4
0
0
1

예제 입력 2

3 3 30
1 2 10 1 1
1 2 1 100 2
3 2 1 100 2

예제 출력 2

701
1
7
7

두 섬을 연결하는 다리가 여러 개 있을 수도 있다.