时间限制：$2s$,，空间限制：$512MB$

题目描述

​ 小F和小Y去公园游玩，公园里一共有$n$个景点，有$m$条双向道路（可能出现重边和自环）。

​ 初始时小F和小Y在$1$号景点，能量值为q，经过每条道路会消耗一定的能量值，能量值不能低于0，在此基础上小Y希望小F求出到达每一个景点的最短路，小F口算不出来了，决定求助于你。

输入格式

​ 输入文件名位$garden.in$。

​ 输入文件的第一行包含两个正整数$n,m,q$，表示有$n$个景点，$m$条双向道路，初始能量值为q。

​ 接下来的$m$行每行包含$4$个正整数$x,y,z,c$，表示$x$和$y$之间有一条长为$z$的道路，经过这条道路需要消耗c的能量值。

输出格式

​ 输出文件名为$garden.out$

​ 输出$n$个正整数，第$i$个正整数表示从$1$号点到$i$号景点的最短路，若无法到达输出$-1$。

样例

样例1

输入数据：

4 4 1
1 2 3 1
1 3 2 1
2 4 5 0
4 3 1 1

输出数据：

0 3 2 8

样例2

见选手目录下的garden2.in和garden2.ans

数据范围与约定

​ 对于$20\%$的数据，满足$n\le 5,\ m\le 8$。

​ 对于另$30\%$的数据，满足$c=0$。

​ 对于另$30\%$的数据，满足$c\ne 0$。

​ 对于$100\%$的数据，满足$1\le n\le 10^5,\ 1\le m\le 2*10^5,\ 0\le c\le q \le 10,\ 1\le z\le 10^9$。

样例下载