P3511 [POI 2010] MOS-Bridges

San Bytecisco 是一个风景优美的沿海小镇。 它由一些小而人口稠密的岛屿组成，编号从 $1$ 到 $n$。 某些岛屿之间通过桥梁连接，用于双向的道路交通。 每对岛屿之间最多可以有一座桥。 这些岛屿的连接方式使得每个岛屿都可以通过桥梁到达其他岛屿。 Byteasar 和 Bytie 正计划在 San Bytecisco 骑自行车旅行。 他们将从 $1$ 号岛出发。 他们打算访问每个岛屿，同时每座桥只经过一次，并在旅行结束时回到出发地，即 $1$ 号岛。 作为经验丰富的骑手，他们预计会遇到一些严重的麻烦……风！ 毕竟，沿海地区风很大，尤其是在岛屿之间的桥上。显然，根据风速和方向，风会在不同程度上使得跨越桥梁变得困难。 为了简单起见，我们假设每座桥和每个跨越方向的逆风速度是恒定的。 帮助 Byteasar 和 Bytie 找到他们想要的路线，并且这条路线的疲劳程度最小。Byteasar 和 Bytie 同意将最大逆风速度作为路线疲劳程度的衡量标准。

标准输入的第一行有两个用空格分隔的整数：$n$ 和 $m$（$2 \le n \le 1000$，$1 \le m \le 2000$），分别表示 San Bytecisco 的岛屿数量和桥梁数量。岛屿编号从 1 到 $n$，桥梁编号从 1 到 $m$。接下来的行指定了桥梁。第 ($n+1$) 行包含四个用空格分隔的整数 $a_i,b_i,l_i,p_i$（$1 \le l_i,p_i \le 1000$），表示第 $i$ 号桥连接了第 $a$ 号和第 $b$ 号岛屿。当从 $a$ 到 $b$ 移动时的逆风速度为 $l_i$，而从 $b$ 到 $a$ 移动时的逆风速度为 $p_i$。

如果没有满足这两位勇敢骑手要求的路线，标准输出的第一行应为单词 NIE（波兰语中的“不”）。 否则，输出应有两行，指定 San Bytecisco 上最不疲劳的路线。 第一行应包含该路线的最大逆风速度，即我们希望最小化的数字。 第二行应包含 $m$ 个整数，用空格分隔，给出在最不疲劳的路线中依次经过的桥梁编号。 如果有多条最不疲劳的路线，程序可以任意选择一条。

$2 \le n \le 1000$，$1 \le m \le 2000$，$1 \le a_i,b_i \le n$，$a_i\neq b_i$，$1 \le l_i,p_i \le 1000$。 题面翻译由 ChatGPT-4o 提供。