U474182 Erdaz 与电车难题（？暂无多项式复杂度？）

Eradz 进行电车难题。

Erdaz 现在是一个电车难题中的电车司机。 这个难题中有 $n$ 个站点，$m$ 条轨道，且轨道是双向通行的。 现在 Erdaz 要接送乘客，他需要在规定时间内从站点 $1$ 到站点 $n$ 。 但是在第 $i$ 个轨道上绑了 $a_i$ 个人，而通过这条轨道的时间是 $t_i$ 。 因为超时会扣钱，所以 Erdaz 希望你在消耗时间不超过 $k$ 的情况下让碾过的人最少。

第一行三个正整数 $n,m,k$ 。 接下来 $m$ 行，每行四个正整数 $u_i,v_i,a_i,t_i$，表示在站点 $u_i$ 和站点 $v_i$ 之间有一条绑了 $a_i$ 个人，通过时间是 $t_i$ 的双向轨道。

一个正整数，表示从站点 $1$ 到站点 $n$ 的所有消耗时间不超过 $k$ 的路径中碾过的人数的最小值。 若无法在消耗时间不小于 $k$ 时到达 $n$ 号站点，输出 ```-1``` 。

|测试点编号|$\le$|$\le$|特殊性质|a|a|a|a|a |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$\sim$|$$|$$|无|a |$\sim$|$$|$$|A|a |$\sim$|$$|$$|无|a |$\sim$|$$|$$|无|a |$\sim$|$$|$$|无|a |$\sim$|$$|$$|无|a |$\sim$|$$|$$|$$| |$\sim$|$$|$$|无|a 板子，别管先。 //ai = ti+1， k为ai最短路 ，ti只有01，树 保证每两个站点之间至多只有一条轨道，且每个站点都可以互相到达。