UVA1728 Toll Management IV

#### 题目大意 给一张 $N$ 个点 $M$ 条边的无向图，每条边权值为 $C_i$ 。前 $N-1$ 条边为该图的最小生成树。 对于第 $i$ 条边，若边权分别增加和减少 $A_i,B_i$ ，且不改变最小生成树形态，求 $A_i$ 和 $B_i$ 的最大值。

第一行一个整数 $T$ ，表示测试组数。 每组测试中，第一行两个整数 $N,M$ ，分别表示这张图的点数和边数。 接下来 $M$ 行中，每行有三个整数 $U_i,V_i,C_i$ ，表示 $U_i,V_i$ 之间有一条权值为 $C_i$ 的边。

对于每一组测试，输出一个整数 $S$ ，其意义如下 $$ S=\sum_{i=1}^{M}{(i\times A_i+i^2\times B_i)} $$ 特别的，若 $A_i$ 或 $B_i$ 不存在，在上式中用 $-1$ 代替 具体格式参见样例 #### 样例输入 ```plain 2 3 3 1 2 5 2 3 7 1 3 10 4 5 1 3 1 3 4 2 1 2 3 1 4 4 2 4 5 ``` #### 样例输出 ```plain Case 1: 30 Case 2: 72 ```

$T