[AHOI2006]上学路线route

可可和卡卡家住在合肥市东郊，每天上学都要转乘多次公交车才能到达市区西端的学校。直到有一天，他们参加了学校的信息学奥林匹克竞赛小组，才发现每天上学的乘车路线不一定是最优的。

合肥市共有 $N$ 个公交车站，编号为 $1$ 至 $N$。可可和卡卡家住在 $1$ 号车站附近，学校位于 $N$ 号车站。市内共有 $M$ 条直达公交路线，第 $i$ 条路线往返于车站 $p_i$ 和 $q_i$ 之间，从一个端点到另一个端点需要花费时间 $t_i$。

两人根据这些信息很快编写出了程序，计算出最优的乘车方案。然而，可可想趁卡卡不备，从卡卡的输入数据中删除一些公交路线，使卡卡的程序计算出的最短时间大于实际的最短时间。对于每条路线 $i$，都有一个代价 $c_i$，删除代价越大的路线，卡卡就越容易发现这个玩笑。

请你计算出实际从家到学校所需的最短时间，并设计一种删除方案，使删除后从家到学校的最短时间变大，同时使被删除路线的代价之和最小。

输入文件中第一行有两个正整数 $N$ 和 $M$，分别表示公交车站数和公交路线数。接下来 $M$ 行中，第 $i$ 行描述第 $i$ 条路线，包含四个正整数 $p_i$、$q_i$、$t_i$ 和 $c_i$，具体含义如题目描述所述。

输入格式

第一行包含两个正整数 $N$ 和 $M$。

接下来 $M$ 行，每行包含四个正整数 $p_i$、$q_i$、$t_i$ 和 $c_i$，表示第 $i$ 条公交路线往返于车站 $p_i$ 和 $q_i$ 之间，行驶时间为 $t_i$，删除该路线的代价为 $c_i$。

输出格式

输出最多两行。

第一行输出一个整数，表示从家到学校的实际最短时间。

第二行输出一个整数 $C$，表示被删除路线的代价之和的最小值。

样例输入

6 7
1 2 1 3
2 6 1 5
1 3 1 1
3 4 1 1
4 6 1 1
5 6 1 2
1 5 1 4

样例输出

2
5

数据范围

• $2\le N\le 500$；
• $1\le M\le 124750$；
• $1\le t_i,c_i\le 10^4$；
• 合肥市的公交网络十分发达，可以认为任意两个车站之间都可以通过直达或换乘互相到达；
• 如果删除路线后，家和学校无法互相到达，则认为上学所需的最短时间为正无穷大，这是一种合法方案。

来源与许可

本题为 AHOI 2006 试题「上学路线」，题面与测试数据整理自 BZOJ $1266$。

样例 1

输入

6 7
1 2 1 3
2 6 1 5
1 3 1 1
3 4 1 1
4 6 1 1
5 6 1 2
1 5 1 4

输出

2
5