K - Tree Minimization Problem

2 secs 1024 MB
uni_kakurenbo

配点:

問題文


から までの番号のついた 個の頂点と, 個の辺からなる,連結な重み付き無向グラフがあります.

を満たす任意の整数 について,頂点 と頂点 とを結ぶ,重み の辺が存在します.ただし です.

また,長さ 正整数列 があり,このとき整数 に対して を次のように定めます:

  • 頂点 と頂点 とを結ぶ単純パスに含まれる辺の重みの総和

さらに,任意の重み付きグラフに対して以下の操作を行うことができます:

操作

  • 好きな辺を つ選択し,その辺の重みを で置換する.

このグラフに対して,以上の操作 回以上 回以下行うとき, の値は最小でいくつにすることができますか?
求めてください.

制約


  • 入力はすべて整数

入力


各テストケースの入力は,それぞれ以下の形式で与えられる:










出力


答えを出力せよ.

サンプル


入力例1
1
9
1 1
2 4
2 3
3 1
3 5
6 1
6 6
6 2
6
3 4
1 5
6 9
2 8
3 9
4 8
出力例1
39

頂点 を結ぶ辺に対して操作を 回行うことが最適です.


入力例2
1
2
1 -1
3
1 2
1 2
1 2
出力例2
-3

提出


Go (1.14)