\begin{problem}{Забег}{run.in}{run.out}{2 секунды}{256 мегабайт}

%Автор задачи: Замятин Евгений
%Автор условия: Замятин Евгений

Команда Людей Икс решила выяснить, кто из них самый быстрый бегун. Для этого они организовали трассу, состоящую из контрольных точек.
Трасса представлена в виде неориентированого графа с $n$ вершинами, обозначающими контрольные точки, и $m$ рёбрами. Для каждого ребра известна его длина. 

По правилам забега каждый участник должен пробежать $k$ контрольных точек так, чтобы последовательность вершин, соответствующих 
им, представляла простой путь. Однако Профессор Икс выяснил, что в системе, регистрирующей участника на контрольной точке, 
есть ошибка. Для каждого участника система запоминает только последнюю посещённую контрольную точку. 
Профессор Икс решил схитрить~--- он решил составить не кратчайший простой путь, а такой маршрут минимальной длины из $k$ контрольных точек, 
что каждые две последовательные точки различны, и между ними есть ребро.

\InputFile
В первой строке входного файла дано два числа $n$ и $m$ ($1 \le n \le 100000, 1 \le m \le 200000$)~--- количество вершин и количество ребер в графе.
В следующей строке дано целое число $k$ ($2 \le k \le 100000$)~--- длина маршрута. 
В $i$-й из следующих $m$ строк дана тройка чисел $a_i, b_i, w_i$ ($1 \le a_i, b_i \le n, 1 \le w_i \le 10000$)~--- описание $i$-го ребра.
Гарантируется, что в графе нет петель.

\OutputFile
Выведите минимальную длину маршрута.

\Example
\begin{example}%
\exmp{
3 3
3
1 2 1
2 3 1
1 3 2
}{
2
}%
\end{example}
\end{problem}