You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

开车回家

题目描述

小明在$1$号城市打工，放假前想回老家所在的$n$号城市，他决定开车回家。这$n$个城市之间有$m$条道路相连，其中有一部分是高速公路，剩下的是普通公路。小明走普通公路不需要付费，但是走高速公路需要付费，好在小明当时买了ETC，里面的钱还能供小明走$k$次高速公路。小明不想额外掏路费，在已知每条路的通行时间$t$的情况下，问小明至少需要多久才能到家？当然，高速公路可能堵车，所以可能比某些普通公路还慢。

输入格式

第一行三个正整数$n,m,k$。后面$m$行每行四个整数$x,y,t,op$表示$x$和$y$之间有一条通过时间为$t$的路，$op=0$表示这条路是普通公路，$op=1$表示这条路是高速公路。

注意输入数据中可能有两个点之间既有普通公路也有高速公路，但是不会存在两个点之间有多条普通公路或多条高速公路的情况。

输出格式

一个整数表示小明回家的最短时间。

样例 #1

样例输入 #1

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

样例输出 #1

3

样例输入 #2

6 8 0
1 5 7 0
1 2 7 0
1 4 2 1
2 6 7 0
2 5 8 0
3 5 6 1
4 5 2 0
5 6 5 1

样例输出 #2

14

样例输入 #3

8 15 2
1 6 93 1
1 7 10 0
1 3 46 1
2 8 34 1
2 6 57 1
2 5 80 0
2 3 61 1
2 4 5 0
3 6 9 1
3 5 22 0
3 4 53 0
3 7 41 0
4 6 100 1
5 7 79 1
5 8 24 1

样例输出 #3

92

提示

样例解释1：

1到2走普通公路，2到3走高速公路，3到4走普通公路，总时长为3，是最小时长。

数据范围

对所有的数据，$1\le n\le 1000,1\le m \le 20000,1\le k\le 100,1\le t\le 10^5$。

特殊性质：普通公路形成的图构成一条链。