### 问题描述 Alice 是 Z 城一个忙碌的快递员，每天得从自己所在的点 $v$ 出发，到达集散地 $0$ 点，从集散地带上所有需要运送的快递，前往一个被指派的地点 $u$ 。 Z 城有完善的交通体系，有许多直接连接两地的单行线和双行线（图中的有向边和无向边），这些边有着不一定相同的长度。同时，其市中心就是集散地 $0$ 点，可以保证所有地点可以到达 $0$ 点，且从 $0$ 点出发可以到达其他所有地点。 抽象地来看，每天 Alice 的路径都是一条经过 $0$ 点且起点终点非 $0$ 点的路径。 对于所有的满足 $1\leq u,v\leq n$ 的 $(u,v)$ 我们都可以得到从 $u$ 经过 $0$ 到达 $v$ 的最短路径，记其长度为 $d(u,v)$ 。现在 Alice 想知道对于所有的对 $(u,v)$，$d(u,v)$ 的第 $k$ 小值是多少，请你为她计算一个对应的结果。 ### 输入格式 第一行包含三个整数 $n,m,k$，$n$ 表示 Z 城中除了 $0$ 点外的的地点个数，$m$ 表示直达路径数量，$k$ 表示要求是第 $k$ 小的数值。 接下来第 $2$ 到 $m+1$ 行表示图中的所有路径，每行有四个整数 $type, u, v, w$。其中 $type$ 表示这条边是否是有向边，如果为 $0$ 则是无向边，如果为 $1$ 则是有向边。如果是有向边，则这条边为从 $u$ 到 $v$ 的长度为 $w$ 的边；否则，这条边为连接 $u,v$ 的长度为 $w$ 的边。 ### 输出格式 包含一个整数，表示第 $k$ 小的 $d(i,j)$。 ### 样例输入 ```text 3 5 3 0 0 1 3 0 1 2 5 0 1 3 6 1 2 3 1 1 3 0 3 ``` ### 样例输出 ```text 7 ``` ### 说明 根据寻找最短路，我们得到 $d(1,1)=6, d(1,2)=11, d(1,3)=12, d(2,1)=6, d(2,2)=11, d(2,3)=12, d(3,1)=7, d(3,2)=12, d(3,3)=13$，其中第 $3$ 小的数值为 $7$ 。 ### 评测数据规模 对于 $20\\%$ 的评测数据，$1\leq n\leq 2\times 10^3, 1 \leq m \leq 4\times 10^3$。 对于 $100\\%$ 的评测数据，$1\leq n\leq 5\times 10^4, 1 \leq m \leq 10^5$ 。 对于全部的评测数据，均有 $1\leq w \leq 10^4, 1\leq k \leq n^2$ 。