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$번 패턴을 의미하는 $3$개의 정수 $i,j,x$가 공백으로 구분되어 주어진다. $(1\le i<j\le N;$ $0\le x\le 10^9)$

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