San Bytecisco 是一个风景优美的沿海城镇。它由 $n$ 个面积虽小但人口稠密的岛屿组成，编号从 $1$ 到 $n$。某些岛屿之间由桥梁连接，用于（双向）道路交通。每对岛屿之间最多只有一座桥。这些岛屿的连接方式保证了从任意一个岛屿出发，仅通过桥梁即可到达其他所有岛屿。

Byteasar 和 Bytie 计划在 San Bytecisco 进行一次自行车旅行。他们将从 $1$ 号岛屿出发。他们打算访问每一个岛屿，且每座桥恰好经过一次，最后回到出发点，即 $1$ 号岛屿。作为经验丰富的骑手，他们预料到会遇到一些严重的麻烦……风！毕竟，沿海地区风很大，桥梁上的风尤其强劲。显然，根据风速和风向的不同，风在不同方向上对过桥造成的阻碍程度也不同。为简化起见，我们假设对于每一座桥和每一个通行方向，逆风速度都是恒定的。

请帮助 Byteasar 和 Bytie 找到一条符合他们要求的路线，并使其尽可能轻松。Byteasar 和 Bytie 同意将路线中遇到的最大逆风速度作为衡量路线疲劳程度的标准。

输入格式

输入的第一行包含两个由空格分隔的整数：$n$ 和 $m$ ($2 \le n \le 1\,000$, $1 \le m \le 2\,000$)，分别表示 San Bytecisco 的岛屿数量和桥梁数量。岛屿编号为 $1$ 到 $n$，桥梁编号为 $1$ 到 $m$。接下来的 $m$ 行描述桥梁信息。第 $(i+1)$ 行包含四个由空格分隔的整数 $a_i, b_i, l_i, p_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$, $1 \le l_i, p_i \le 1\,000$)。这表示第 $i$ 号桥连接 $a_i$ 和 $b_i$ 号岛屿。当从 $a_i$ 移动到 $b_i$ 时，逆风速度为 $l_i$；当从 $b_i$ 移动到 $a_i$ 时，逆风速度为 $p_i$。

输出格式

如果不存在满足这两位勇敢骑手要求的路线，则输出的第一行（也是唯一一行）应包含单词 NIE（波兰语中的“不”）。否则，输出应包含两行，指定 San Bytecisco 中最轻松的路线。第一行应包含该路线的最大逆风速度，即我们希望最小化的数值。第二行应包含 $m$ 个由空格分隔的整数，给出在最轻松路线上依次经过的桥梁编号。

如果存在多条最轻松的路线，你的程序可以任意选择其中一条。

样例

输入格式 1

4 4
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4

输出格式 1

4
4 3 2 1