题目描述

断罪小学所在的城市治安十分混乱，有些街道已经被小混混占据。这些被占据的道路各自有一个“武力值下限”，如果行人的武力值低于这个下限，那么他就会被小混混们抢劫并且痛打一顿；否则，行人可以安全通过。没有被占据的道路的“武力值下限”为0。
城市内有\(n\)个居民区，编号为\(1 \sim n\)。两个居民区之间可能有道路直接相连，共计\(m\)条道路，每条道路都有一定的长度。断罪小学位于1号居民区。
断罪小学的大队长接到了来自校方的通知，要求派人前往\(n\)号居民区采购物资。大队长手下有\(k\)个人可供差遣，由于社会险恶，一个人出行可能不安全，所以需要选出其中一些人组队（至少1人），整个队伍的武力值等于每个成员的武力值之和。
大队长得到了城市所有道路的信息，包括每条路连接的两个居民区、道路长度和“武力值下限”。大队长希望队伍尽早到达目的地，所以路径的总长度越短越好。然而，这\(k\)个人向来明争暗斗，大队长深知人越多越不可靠，所以他希望派遣的人数尽可能少。
经过深思熟虑，他决定把安排工作交给了会编程的你。请你编写程序求出大队长至少需要派遣多少人，以及在人数最少的前提下所需的最短路程。如果无论如何安排都不可能安全到达\(n\)号居民区，输出-1。

格式

输入格式

每个输入文件包含多组测试数据。
文件的第一行是测试数据的组数\(T\)，之后对于每组测试数据：
第一行是3个正整数\(n,m,k\)；
第二行是\(k\)个非负整数，表示\(k\)个人各自的武力值；
之后\(m\)行，每行4个非负整数：\(u,v,w,d\)，表示\(u\)号和\(v\)号居民区之间有道路直接相连，该道路的“武力值下限”为\(w\)，道路长度为\(d\)。输入保证无重边和自环。

输出格式

每组测试数据输出一行。
若存在能够安全到达\(n\)号居民区的派遣方案，输出两个正整数，之间以一个空格隔开。前一个为最少需要派遣的人数，后一个为人数最少前提下的最短路径。
若无法安全到达\(n\)号居民区，输出-1。

样例

输入

1
4 4 10
23 29 17 14 31 13 28 26 20 22
1 2 60 40
1 3 55 35
2 4 75 15
3 4 55 45

输出

2 80

数据规模及限制

时间限制1s，空间限制64MB。
共10个测试文件，每个文件包含\(3 \sim 5\)组测试数据。
所有数据均满足：\(w \le 10^9\)，\(k\)个人的武力值之和\( \le 10^9\)，所有道路的长度均为正整数，且长度之和\(\le 10^9\)。
测试文件#1：\(n \le 20, \quad m \le 50, \quad k \le 10\)
测试文件#2\(\sim\)#4：\(n \le 1000, \quad m \le 5000, \quad k \le 10000\)
测试文件#5\(\sim\)#6：\(n \le 10000, \quad m \le 50000, \quad k \le 10\)
测试文件#7\(\sim\)#10：\(n \le 10000, \quad m \le 50000, \quad k \le 10000\)

来源

2017.7 太原五中高一集训
Originally created by Orina_zju@163.com