P0921

[Balkan 2011]Timeismoney

[Balkan 2011]Timeismoney

有 nn 个城市，编号为 00 到 n−1n-1，城市之间有 mm 条双向公路。你需要从中选择 n−1n-1 条公路，使任意两个城市之间均可互相到达，即所选公路构成一棵生成树。

每条公路都有费用 cc 和耗时 tt。定义一个方案的权值为所选公路的费用总和与耗时总和的乘积。请找到权值最小的方案。

输入格式

第一行包含两个整数 n,mn,m，分别表示城市数量和公路数量。

接下来 mm 行，每行包含四个整数 a,b,c,ta,b,c,t，表示城市 aa 与城市 bb 之间有一条双向公路，其费用为 cc，耗时为 tt。

输出格式

输出一行两个整数 sumcsumc 和 sumtsumt，分别表示所选生成树的费用总和与耗时总和。

首先最小化 sumc×sumtsumc\times sumt；若有多个方案的乘积相同，则选择 sumcsumc 最小的方案；若 sumcsumc 仍相同，则选择 sumtsumt 最小的方案。

样例输入

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≤2001\le n\le 200；
  • 1≤m≤1041\le m\le 10^4；
  • 0≤a,b≤n−10\le a,b\le n-1；
  • 0≤t,c≤2550\le t,c\le 255；
  • 对于 5%5\% 的数据，满足 m=n−1m=n-1；
  • 对于 40%40\% 的数据，满足 t=ct=c；
  • 保证给定的无向图连通，因此至少存在一棵生成树。

来源与许可

本题为 Balkan 2011 试题「Timeismoney」，题面与测试数据整理自 BZOJ。

样例 1

输入

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