Забег

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

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

В первой строке входного файла дано два числа $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$-го ребра. Гарантируется, что в графе нет петель.

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