K-th Shortest Path in a Directed Graph with Allowed Cycles

Given a weighted directed graph with n vertices and m edges, where each edge weight is one of \(1\), \(2\), or \(3\). Consider all possible paths (a path is defined as a sequence of one or more edges and is not required to be simple, i.e. vertices may be repeated) and sort them in non-decreasing order of their total length. Your task is to output the length of the \(k\)-th smallest path.

Note: The vertices are numbered from 1 to n. It is guaranteed that for the given input, the \(k\)-th path exists.

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\) separated by spaces.

Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(w\) describing a directed edge from vertex \(u\) to vertex \(v\) with weight \(w\) (where \(w \in \{1,2,3\}\)).

outputFormat

Output a single integer representing the length of the \(k\)-th smallest path.

sample

3 3 1
1 2 1
2 3 2
1 3 3

1