페루 Machu Picchu의 새 물놀이 공원에서 영감을 받은 Farmer John은 소들을 위해 공원을 짓는다. 가장 큰 명물은 독특하게 설계한 거대한 물 미끄럼틀이다.

$E$개 작은 미끄럼틀 ($1 \le E \le 150,000$)이 $V$개 작은 웅덩이 ($2 \le V \le 50,000$)를 잇고 번호는 $1..V$이다. 정해진 방향으로만 가며 역방향은 불가하다. 소는 1에서 출발해 끝 $V$까지 미끄러진다. 1을 제외한 모든 웅덩이는 진입 하나 이상, $V$를 제외하면 별개의 출구 하나 이상이 있다.

어떤 웅덩이에서도 끝 $V$에 갈 수 있다. 나갔다가 여러 미끄럼틀을 거쳐 같은 웅덩이에 돌아올 수는 없다.

미끄럼틀 $i$는 $P_{i}$에서 $Q_{i}$ ($1 \le P_{i} \le V; 1 \le Q_{i} \le V; P_{i} \ne Q_{i}$)로 가며 재미 $F_{i}$ ($0 \le F_{i} \le 2,000,000,000$)가 있다. Bessie의 총 재미는 거친 모든 값의 합이다.

오래 줄을 서서 최대한 재미있기를 원한다. 보통 출구를 신중히 고르지만 소라서 최대 $K$번 ($1 \le K \le 10$) 제어를 잃어 임의 출구를 따른다. 1에서도 가능하다.

최악의 경우 재미를 최대화해 고르면 얼마를 보장하는가?

웅덩이 3개 (대괄호는 번호), 미끄럼틀 4개, $K$가 1인 예이다. 괄호 밖은 재미이다.

          [1]
         /   \
   5 -> /     \ <- 9
       /       \
     [2]---3---[3]
        \__5__/

항상 1에서 3으로 간다. 자유롭게 고르면 1에서 2, 재미 5의 좋은 출구로 3에 가서 $5+5=10$이다. 1에서 제어를 잃으면 곧장 3으로 가서 9, 2에서는 $5+3 = 8$만 얻을 수도 있다.

$1\to3$을 골라 9를 얻는다. 1에서 제어를 잃어 $1\to2$로 가면 2에서는 다시 잃지 않아 10이다. 따라서 최소 9를 보장한다.

입력

• $1$번째 줄: 공백 구분 정수 $V$, $E$, $K$.
• $2..E + 1$번째 줄: $i+1$번째 줄에는 공백 구분 정수 $P_{i}$, $Q_{i}$, $F_{i}$.

출력

• $1$번째 줄: Bessie가 보장하는 최소 재미인 정수 하나.

예제

입력 1

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

출력 1

9

문제 출제자: John Pardon, 2010