### 问题描述

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)$。

样例输入

3 5 3
0 0 1 3
0 1 2 5
0 1 3 6
1 2 3 1
1 3 0 3

样例输出

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$ 。