AT_s8pc_1_g Revenge of Traveling Salesman Problem

E869120 是一名推销员，为了完成任务，他需要经过所有的建筑物一次，然后返回到起点，也就是他的商店。 在他居住的城镇里，有 $N$ 个建筑物和 $M$ 条道路。建筑物从 1 开始编号，商店位于建筑物 1。 每一条道路 $i$ 连接了建筑物 $s_i$ 和 $t_i$，其长度为 $d_i$。 值得注意的是，为了安全，该镇的某些道路会在一定时间后关闭。 具体来说，E869120 从商店出发后经过时间 $time_i$，第 $i$ 条道路就会关闭。 因此，必须在关闭前通过这些道路。 E869120 想知道：在最短时间内回到商店的方法有多少种？ 最短路径的长度以及以最短时间返回商店的方法总数需要由你来计算。假设 E869120 每单位时间可以移动一单位距离，并且所有道路都是双向通行的。

输入为以下格式： > $N$ $M$ > $s_1$ $t_1$ $d_1$ $time_1$ > $s_2$ $t_2$ $d_2$ $time_2$ > ... > $s_M$ $t_M$ $d_M$ $time_M$ - 第一行包含两个整数 $N$ 和 $M$。 - 接下来的 $M$ 行，每行由四个整数 $s_i, t_i, d_i, time_i$ 组成。

输出包括： - 如果存在满足条件的路径，输出最短路径时间和方法总数，用空格隔开。 - 如果不存在满足条件的路径，输出 "IMPOSSIBLE"。 - 输出结果后加上换行符。

- $1 \leq N \leq 16$ - $1 \leq s_i < t_i \leq N$ - $1 \leq d_i \leq 10^{12}$ - $1 \leq time_i \leq 10^{12}$ - 任意 $i,j$ 满足 $(s_i, t_i) \neq (s_j, t_j)$ ### 部分分数 - 满足 $2 \leq N \leq 8$ 的数据集全部正确，将得到 15 分。 - 剩余数据集全部正确，将得到 85 分。 ### 样例解释 1. 如果路径是 $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$ 或 $1 \rightarrow 3 \rightarrow 2 \rightarrow 1$，都可以用 6 个单位时间完成，这是最短路径。 2. 由于道路 1 在 1 单位时间后关闭，因此路径 $1 \rightarrow 3 \rightarrow 2 \rightarrow 1$ 无法完成。 3. 如果路径 $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$ 或 $1 \rightarrow 3 \rightarrow 2 \rightarrow 1$ 都不可行，那么 E869120 无法完成任务。 **本翻译由 AI 自动生成**