Minimizing Road Trip Distance

You are given a set of n cities and m bidirectional roads connecting some pairs of these cities. Each road has an associated length. You are also given an integer k which represents the number of distinct cities you must visit during your trip. Your task is to find a cycle (a tour that starts and ends at the same city) that visits exactly k distinct cities (including the starting city) and minimizes the total distance traveled.

If such a journey exists, print the sequence of cities visited (including the starting city repeated at the end) separated by a space. Otherwise, output -1.

The optimization goal is to minimize the total distance:

$$\min \sum_{i=1}^{L-1} d(city_i, city_{i+1})$$

where L is the length of the journey (i.e. k+1 since the start city is repeated at the end).

inputFormat

The input is given via standard input (stdin) and has the following format:

n m k
u1 v1 l1
u2 v2 l2
... (m lines in total)

Here:

• n is the number of cities.
• m is the number of roads.
• k is the required number of distinct cities to visit.
• Each of the next m lines contains three integers u, v and l indicating that there is a bidirectional road between cities u and v with length l.

outputFormat

Output the resulting tour as a sequence of space-separated city numbers in one line if a valid route exists, otherwise output -1. The tour should start and end at the same city.

## sample

4 5 3
1 2 10
2 3 10
3 4 10
4 1 10
1 3 30

1 2 3 1