SV 필터

NZPC는 물 필터를 만드는 회사다. 필터 안에는 스펀지 같은 재질이 들어 있어서, 빈 공간과 빈 공간을 잇는 통로로 이루어진 구조로 볼 수 있다. 물은 이 통로를 따라 흐른다.

한 고객이 흐르는 물의 양이 지정된 값으로 제한되는 필터, 즉 SV 필터를 주문했다. 필터마다 최대 유량이 정해져 있지만 제조 과정에서 이 값을 맞추기는 어렵다. 그래서 NZPC는 먼저 평범한 방법으로 필터를 만든다. 유량이 너무 낮으면 버리고, 너무 높으면 입구에 입자를 넣는다. 입자는 크기와 연결 구조에 따라 일부 통로를 막는다. 원하는 유량이 나온 필터는 열처리로 입자를 고정한 뒤 고객에게 보낸다.

입자를 넣었다가 실패하면 씻어내는 작업이 오래 걸리고 물도 많이 든다. NZPC는 이 낭비를 줄이려고 CT 스캐너를 들여왔다. 스캐너는 필터 내부의 빈 공간과 통로를 정확한 지도로 만들어 준다. 이 지도를 받아 입자를 넣었을 때 유량이 어떻게 변하는지 계산하는 프로그램을 작성하라.

문제를 다루기 쉽게 다음을 가정한다.

• 모든 크기와 유량은 정수다.
• 빈 공간은 가장 큰 입자도 자유롭게 지나갈 만큼 넓다.
• 입자는 통로에 끼어서 통로를 막는다. 입자의 크기가 통로의 용량과 정확히 같을 때만 끼인다.
• 크기가 용량보다 큰 입자는 그 통로를 지나가지 못하고, 막지도 못한다.
• 크기가 용량보다 작은 입자는 그 통로를 자유롭게 지나간다.
• 스캐너가 준 지도는 빈 공간이 정점이고 통로가 간선인 그래프다. 정점 $0$이 입구, 정점 $1$이 출구다.
• 통로마다 정수 용량 $C$가 하나 있고, 이 값이 그 통로로 흐를 수 있는 최대 유량이다.
• 물은 통로를 양쪽 어느 방향으로든 흐를 수 있다.

크기가 $P$인 입자를 입구에 충분히 많이 넣는다. 입자가 닿을 수 있는 통로 가운데 용량이 $P$인 통로는 모두 막힌다. 이를 정확히 쓰면 다음과 같다.

• 정점 $0$에서 출발해 용량이 $P$보다 큰 통로만 지나서 갈 수 있는 정점을 도달 가능한 정점이라고 한다.
• 용량이 정확히 $P$인 통로는 양 끝 정점 가운데 하나라도 도달 가능하면 막힌다. 출구인 정점 $1$도 이 판정에서는 다른 빈 공간과 똑같이 취급한다.
• 나머지 통로는 그대로 남는다.

막힌 통로를 모두 지운 그래프에서 입구부터 출구까지의 최대 유량을 다시 구하면, 그 값이 입자를 넣은 뒤의 유량이다.

그림은 첫 번째 예제를 그린 것이다. 정점에 적힌 수는 번호이고, 간선에 적힌 두 수는 용량과 실제로 흐르는 양이다. 왼쪽 그래프에서 입구부터 출구까지의 최대 유량은 $7$이다. 정점 $2$와 정점 $4$를 잇는 간선의 흐름은 음수로 적혀 있는데, 그림에서 아래쪽이 아니라 위쪽으로 거슬러 흐른다는 뜻이다. 오른쪽 그래프는 크기가 $5$인 입자를 넣은 뒤의 모습이다. 정점 $2$와 정점 $4$를 잇는 간선이 막혀서 점선으로 그려졌고, 최대 유량은 $2$로 떨어졌다.

입력은 필터 여러 개로 이루어진다. 각 필터는 정수 $N$, $E$, $P$가 적힌 줄로 시작한다. $N$ $(3 \le N \le 1000)$은 빈 공간의 수, $E$ $(3 \le E \le 2000)$는 통로의 수, $P$ $(1 \le P \le 6)$는 필터에 넣을 입자의 크기다.

이어서 $E$개의 줄에 통로가 하나씩 주어진다. 각 줄에는 정수 세 개가 있고, 앞의 두 수는 그 통로가 잇는 두 빈 공간의 번호, 마지막 수는 통로의 용량 $C$다. 빈 공간의 번호는 $0$부터 $N-1$까지이며 $0$번이 입구, $1$번이 출구다. 용량 $C$는 양의 정수다. 같은 두 빈 공간을 잇는 통로가 여러 개일 수도 있다.

입력의 끝에는 $0$이 세 개 적힌 줄이 온다.

필터마다 한 줄에 정수 두 개를 공백으로 구분해 출력한다. 첫 번째 수는 입자를 넣기 전 필터의 최대 유량이고, 두 번째 수는 크기가 $P$인 입자를 넣은 뒤의 최대 유량이다.