Island Cities

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

다리 강화 작업에 사용할 수 있는 예산 $B$가 주어진다. 각 다리는 강화 작업을 할 때마다 $y_i$만큼의 비용을 들여 견딜 수 있는 하중을 $x_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$번 다리를 몇 번 강화해야 하는지 출력한다. 정답이 여러 개라면 그중 하나만 출력한다.