Farmer John codziennie sumiennie sprawdza krowy. Przechodzi niektórymi spośród $M$ $(1 \le M \le 50,000)$ szlaków, ponumerowanych $1,\ldots,M$, od pastwiska $1$ aż do pastwiska $N$ (dla map szlaków w danych testowych taka podróż jest zawsze możliwa). Na farmie Farmer John jest $N$ $(1 \le N \le 10,000)$ pastwisk o numerach $1,\ldots,N$, obecnie połączonych dwukierunkowymi szlakami gruntowymi. Każdy szlak $i$ łączy pastwiska $P1_{i}$ i $P2_{i}$ $(1 \le P1_i \le N; 1 \le P2_i \le N)$, a jego przejście zajmuje $T_{i}$ $(1 \le T_{i} \le 1,000,000)$ jednostek czasu.

Chce zmodernizować część szlaków na swojej farmie, aby zaoszczędzić czas podczas długiej podróży. Konkretnie wybierze $K$ $(1 \le K \le 20)$ szlaków i przekształci je w drogi szybkiego ruchu, co faktycznie zmniejszy czas ich przejścia do $0$. Pomóż FJ wybrać szlaki do modernizacji, aby zminimalizować czas dotarcia z pastwiska $1$ do $N$.

Wejście

• Wiersz 1: trzy liczby całkowite oddzielone spacjami: $N$, $M$ i $K$.

• Wiersze $2,\ldots,M+1$: wiersz $i+1$ opisuje szlak $i$ trzema liczbami całkowitymi oddzielonymi spacjami: $P1_{i}$, $P2_{i}$ i $T_{i}$.

Wyjście

• Wiersz 1: długość najkrótszej ścieżki po zmodernizowaniu nie więcej niż $K$ krawędzi.

Przykład

Wejście 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

Wyjście 1

1

Uwagi

$K$ wynosi $1$; zmodernizuj szlak $3->4$, aby jego czas wynosił $0$ zamiast $100$. Nowa najkrótsza ścieżka to $1->3->4$, a łączny czas jej przejścia wynosi teraz $1$.

Autor zadania: Percy Liang, 2008