#2395. [Balkan 2011]Timeismoney

题目描述

 有n个城市(编号从0..n-1)，m条公路(双向的)，从中选择n-1条边，使得任意的两个城市能够连通，一条边需要的c的费用和t的时间，定义一个方案的权值v=n-1条边的费用和*n-1条边的时间和，你的任务是求一个方案使得v最小

输入格式

第一行两个整数n,m,接下来每行四个整数a,b,c,t,表示有一条公路从城市a到城市b需要t时间和费用c

输出格式

【output】timeismoney.out

仅一行两个整数sumc，sumt,（sumc表示使得v最小时的费用和，sumc表示最小的时间和） 如果存在多个解使得sumc*sumt相等，输出sumc最小的

样例

样例输入

5 7  

0 1 161 79  

0 2 161 15  

0 3 13 153  

1 4 142 183  

2 4 236 80  

3 4 40 241  

2 1 65 92  

样例输出

279 501  

数据范围与提示

【数据规模】

1<=N<=200

1<=m<=10000

0<=a,b<=n-1

0<=t,c<=255

有5%的数据m=n-1

有40%的数据有t=c

对于100%的数据如上所述