小明迷上了一个搭建电路的游戏。
在游戏中,两个电子元件之间只能存在唯一通路,每次在两个电子元件之间增加一条有效电路(两个元件之间先前没有电路相连)都将获得相应的积分奖励。(初始状态时电子元件之间均末连接)
已知电子元件数量n和部分电子元件之间的奖励积分值。如何构建一个有效电路将所有元件全部连接起来,并且可以得到最多的积分奖励
第1行输入两个正整数n和m,其中n表示电子元件数量(n≤100),m表示提供了m对电子元件之间的奖励积分值(m≤1000)。两个正整数之间用空格隔开。
第2行到第m+1行对应m对电子元件及其对应的奖励积分值,每一行包含三个正整数,第1个和第2个整数表示电子元件编号(从1开始),第3个整数表示两个元件之间搭建电路的奖励积分num(0<num<1e9)。整数之间用空格隔开
输出占1行,输出一个正整数,即最多可以得到的积分奖励值。如果没有办法把所有元件全部连接起来,则输出"No solution."(注意,tion后有英文句号)。
输入
3 3
1 2 10
1 3 20
2 3 30
输出
50
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.