正如官方题解所言，为了避免同一次调整中割多条边的情况，需要给网络中的每一条边的容量都加上一个足够大的数，例如题解中用的是 $10^{10}$。

但由于有人用 $10^5$ 过了，所以在此特提醒一下：这个数至少得是 $10^9$ 级别！

构造的话，可以看下面的一组数据：

Input

5 3 4
100000 1 1 1 100000
1 2 2 1
1 3 2 1
2 1 1 2
3 1 1 2

Output

200001

如果使用 $10^5$ 的话，那么结果应该会是 $100004$，即第一次调整第二个和第四个，第二、三次各调整第二、三、四中的某一个，与题意不符。

同理，可以构造出加上的数至少得是 $O(k\max\{a\})$ 级别的数据。

另一方面，由于答案不会超过 $10^9$，所以 $10^9$ 是足够大的。