Pay2Win

하이비는 최근 새로운 게임을 만들었다. 이 게임은 현찰을 사용해야 하는 일명 Pay2Win 게임이다.

게임 개발을 마무리하는 하이비에게는 보스전만 남았고, 보스전의 패턴은 미리 계획해 두었다. 하이비가 계획한 보스전 패턴은 다음과 같다.

• 보스 스테이지는 $N$개의 구역으로 나뉘어 있으며, 플레이어는 하이비가 선택한 시작 위치에서 시작한다.
• 보스는 $K$개의 패턴을 사용하며, 각 패턴의 번호는 $K$ 이하의 서로 다른 양의 정수이다.
• 보스는 모든 패턴을 번호순으로 하나씩 사용한다. 각 패턴은 $(i,j,x)$로 표현하며, $i$번 위치와 $j$번 위치를 바꾸는 패턴이다. 즉, 플레이어가 $i$번 위치에 있었다면 $j$번 위치로, $j$번 위치에 있었다면 $i$번 위치로 이동한다. 플레이어는 이 패턴을 $x$원을 지불해 건너뛸 수 있다.
• 보스의 체력은 $H$로 시작하며, 보스의 체력이 $0$이 되면 플레이어의 승리로 게임이 끝난다.
• $K$개의 패턴이 모두 지난 뒤 플레이어가 $N$번 구역에 있으면 플레이어가 보스의 체력을 $1$ 깎는다. 그렇지 않으면 플레이어의 패배로 게임이 끝난다.
• 게임이 끝나지 않은 경우, $K$개의 패턴을 다시 차례로 거친 뒤 플레이어가 $N$번 구역에 있는지 확인하는 작업을 반복한다. 이때 플레이어는 시작 위치로 돌아가지 않지만, 이미 건너뛴 패턴을 다시 건너뛰려면 비용을 다시 지불해야 한다.

하이비는 최대한 많은 수익을 내고 싶어 한다. 그래서 플레이어가 승리하기 위해 지불해야 하는 최소 비용을 최대화하는 시작 위치를 고르려고 한다. 단, 공정한 게임을 위해 시작 위치에서 승리할 수 있는 방법이 있어야 한다.

첫 번째 줄에 구역의 개수 $N$, 패턴의 개수 $K$, 보스의 체력 $H$가 공백으로 구분되어 주어진다. ($1\le N\le 200\,000$, $0\le K\le 200\,000$, $1\le H\le 100$)

두 번째 줄부터 $K$개의 줄에 걸쳐, $p+1$번째 줄에는 보스의 $p$번 패턴을 나타내는 정수 $i$, $j$, $x$가 공백으로 구분되어 주어진다. ($1\le i<j\le N$, $0\le x\le 10^9$)

첫 번째 줄에 하이비가 시작 지점을 적절히 선정했을 때 플레이어가 지불해야 하는 최소 비용을 출력한다.