@dengyaotriangle 大佬的正确性证明看不太懂，自己用描述不太严谨的方法证明了一下。

假设某个链被割了至少两条边，设其中高度最大的边的起点为 $u$。

• 点 $u$ 可以转移到相邻链上并最终到达 $T$，否则这条链上除高度最高的边外都没必要割掉；
• 点 $u$ 可以由 $S$ 到达，否则高度最大的边没必要割掉。

所以这种方案要么不合法，要么非最优。

顺便给出我原以为可以 hack 掉正解的数据：

3 1 3
1
1 10 10
10 1 10
10 1 10
10 10 1

如果只割了四条流量为 $1$ 的边，就可以 $S\rightarrow\dots\rightarrow(1,4)\rightarrow(2,3)\rightarrow(3,2)\rightarrow\dots\rightarrow T$。