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。接下来的行指定了桥梁。第 i 行包含四个用空格分隔的整数 a_i, b_i, l_i, p_i（1 \le l_i, p_i \le 1000），表示第 i 号桥连接了第 a_i 号和第 b_i 号岛屿。当从 a_i 到 b_i 移动时的逆风速度为 l_i，而从 b_i 到 a_i 移动时的逆风速度为 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。