Min-Cost Max-Flow

最小费用最大流问题
首先，我来谈谈自己对这一问题的理解。该问题的核心在于，以边的费用作为权重，在有向图中寻找最短路径，并在该路径上尽可能多地运输货物，即实现最大流量。当某条边的流量达到其容量上限时，这条边将不再具备运输能力，此时只能通过反向边进行调整。接下来重复上述步骤，在每次迭代中寻找费用最低的路径，并在该路径上输送最大可能的流量。当无法再找到新的最短路径时，即可确定整个网络中的最小费用最大流。

当FJ的朋友来到他的农场参观时，他喜欢带他们四处游览。他的农场共有N（1 <= N <= 1000）个区域，编号为1到N，其中第一个区域是他的住所，而最后一个区域则是大型谷仓。农场内共有M（1 <= M <= 10000）条小径连接这些区域。每条小径连接两个不同的区域，并且长度为非零值且小于35,000。

为了最佳地展示农场风光，FJ会从自己的住所出发进行一次游览旅程，并可能经过一些区域后最终抵达谷仓。之后他会再次返回（可能经过一些区域），回到自己的住所。

他希望这次旅程尽可能简短，但不允许重复行走任何一条小径。请计算出满足条件的最短游览路线长度。FJ确信对于任意给定的农场都存在这样的路线。

输入格式：
第一行包含两个用空格分隔的整数：N和M。

接下来的M行中，每行包含三个用空格分隔的整数，分别表示一条小径的信息：起点、终点以及该小径的长度。

输出格式：
输出一个