OI题库

【题目描述】

一个遥远的王国有m条双向道路连接着n个城市，两座城市之间有可能有不止一条道路。m条道路中有n-1条石头路,  m-n+1条泥土路,任意两个城市之间有且仅有一条完全用石头路连接起来的道路。

每条道路都有一个唯一确定的编号，其中石头路编号为1..n-1，泥土路编号为n..m。每条道路都需要一定的维护费，其中第i条道路每年需要Ci的费用来维护。最近该国国王准备只维护部分道路以节省费用。但是他还是希望人们可以在任两个城市间互达。

国王需要你提交维护每条道路的费用，以便他能让他的大臣来挑选出需要维护的道路，使得维护这些道路的费用是最少的。

尽管国王不知道走石头路和走泥土路的区别，但是对于人民来说石头路似乎是更好的选择。为了人民的利益，你希望维护的道路是石头路。这样你不得不在提交给国王的报告中伪造维护费用。你需要给道路i伪造一个费用Di，使得这些石头路能够被挑选。为了不让国王发现，你需要使得真实值与伪造值的差值和尽量小。

国王的大臣当然不是白痴，全部由石头路组成的方案如果是一种花费最小的方案，那么他会选择这种方案。

求出真实值与伪造值的差值和的最小值。

【输入格式】

输入文件的第一行有两个整数N,M(2<=N<=60,N-1<=M<=400)。

接下来的M行每行有三个整数ai,bi,ci，即这条道路的两个端点（1<=ai,bi<=N,ai≠bi），和维护这条路的费用（1<=ci<=10000）.

【输出格式】

输出一行一个正整数，即真实值与伪造值的差值和f的最小值。

【样例输入】

4 5

4 1 7

2 1 5

3 4 4

4 2 5

1 3 1

【样例输出】

6

【提示】

这里的输出格式和SGU上的原题不同，原题中要求输出方案

【来源】

SGU 206 Roads

作者:Andrew Stankevich

来源:Petrozavodsk Summer Trainings 2003

日期:2003-08-23