先二分答案，构建一副新的图。将原图中每个边拆成两条有向边，新的图只保留边权小于答案的边。则问题转化为判断一幅图是否存在欧拉回路，其中边有的有向，有的无向。

根据欧拉回路的性质，一幅有向图有欧拉回路当且仅当每个点度数为偶数。所以可以用网络流来判断是否有欧拉回路。建立超级源，汇点 $s,t$。对于每个边，建立一个新点。$s$ 往新点流容量为 1 的边，代表这条边产生大小为 1 的度数。如果这条边是有向边，则这个点往有向边的终点连容量为 1 的边。如果是无向边，则往两个端点分别连容量为 1 的边。源点再往图上每个点对应的点连容量为 1 的边。最后跑最大流。如果流满了，则有解。

PS：需要判图的连通性。