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

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

Формат входных данных

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

Формат выходных данных

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

Пример