29105번 - Забег 다국어

문제

Команда Людей Икс решила выяснить, кто из них самый быстрый бегун. Для этого они организовали трассу, состоящую из контрольных точек. Трасса представлена в виде неориентированого графа с $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$-го ребра. Гарантируется, что в графе нет петель.

출력

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

제한

힌트