每次下雨的时候，John的农场里就会形成一个池塘。因此，John修建了一套排水系统，雨水被排到了附近的一条小河中。John还在每条排水沟的起点安装了调节阀门，控制流入排水沟的水流的速度。John不仅知道每条排水沟每分钟能排多少加仑的水，而且还知道整个排水系统的布局。池塘里的水通过这个排水系统排到排水沟，并最终排到小河中，构成一个复杂的排水网络。给定排水系统，计算池塘能通过这个排水系统排水到小河中的最大流水速度。每条排水沟的流水方向是单方向的，但在排水系统中，流水可能构成循环。

输入文件包含多个测试数据。每个测试数据的第1行为两个整数 M 和 N (0≤M≤200，2≤N≤200)，其中 M 是排水沟的数目，N 是这些排水沟形成的汇合结点数目。结点 1 为池塘，结点 N 为小河。接下来有 M 行，每行描述了一条排水沟，用 3 个整数来描述，分别为S_i、E_i 和 C_i，其中 S_i 和E_i (1≤S_i, E_i≤N)标明了这条排水沟的起点和终点，水流从 S_i 流向 E_i，C_i (0≤C_i≤10 000 000) 表示通过这条排水沟的最大流水速度。

对每个测试数据，输出一行，为一个整数，表示排水系统从池塘排出水的最大速度。