[POI2015] WYC

题目描述

给定一张 $n$ 个点 $m$ 条边的带权有向图,每条边的边权只可能是 $1$,$2$,$3$ 中的一种。 将所有可能的路径按路径长度排序,请输出第 $k$ 小的路径的长度,注意路径不一定是简单路径,即可以重复走同一个点。

输入输出格式

输入格式


第一行包含三个整数 $n,m,k$($1\le n\le 40$,$1\le m\le 1000$,$1\le k\le 10^{18}$)。 接下来 $m$ 行,每行三个整数 $u,v,c$($1\leq u,v\leq n$,$u\neq v$,$1\le c\le 3$),表示从 $u$ 出发有一条到 $v$ 的单向边,边长为 $c$。 **可能有重边**。

输出格式


包含一行一个正整数,即第 $k$ 短的路径的长度,如果不存在,输出 $-1$。

输入输出样例

输入样例 #1

6 6 11
1 2 1
2 3 2
3 4 2
4 5 1
5 3 1
4 6 3

输出样例 #1

4

说明

**【样例解释】** 长度为 $1$ 的路径有 $1\to 2$,$5\to 3$,$4\to 5$。长度为 $2$ 的路径有 $2\to3$,$3\to4$,$4\to5\to3$。长度为 $3$ 的路径有 $4\to6$,$1\to2\to3$,$3\to4\to5$,$5\to3\to4$。长度为 $4$ 的路径有 $5\to3\to4\to5$。 ---- 原题名称:Wycieczki。