#最大流 ## 题目描述 好渴鹅正在 [[简介|城市天际线]] II 当中设计立交桥。现在好渴鹅的立交桥上面有 $n$ 个结点，现在有 $m$ 条单向的公路/匝道连接着一定的两个结点。现在你知道这 $m$ 条公路连接的结点编号 $u$ 与 $v$ 以及这条公路的车道数 $w$，这代表着这条公路上面任意一个点都可以同时走 $w$ 辆车，也就是 $u$ 到 $v$ 的最大车流量为 $w$。 假如一个结点的后继有多条，那么你可以将这个结点的车流量分给后继结点。例如 $x$ 可以到 $y$ 和 $z$，而 $s$ 到 $x$ 的最大车流量为 $a$，对于任意一个 $0\le b\le a$ 的正整数，可以将 $b$ 的车流量分到 $x$ 、$a-b$ 的车流量分到 $y$，只要最大车流量最大。 假如一个结点的前继有多条，那么所有前继的车流量会汇流到这里，即将所有前继的最大车流量加起来即可。 对于一条链，这条链的最大车流量是这条链上所有边的车流量的最小值。 请问你从 $s$ 结点到 $t$ 结点的最大车流量是多少。 ## 格式 ### 输入格式 > [!info] 信息 > $n,m$ > $u_1, v_1, w_1$ > $u_2, v_2, w_2$ > $\cdots$ > $u_m, v_m, w_m$ ### 输出格式 > [!info] > 一行一个 $ans$，表示 $s$ 到 $t$ 的最大车流量。 ## 数据范围 - $1\le n, m\le 10^5$ - $1\le u_i, v_i\le n$ - $1\le w_i\le 10^9$