AT_s8pc_1_g Revenge of Traveling Salesman Problem

[problemUrl]: https://atcoder.jp/contests/s8pc-1/tasks/s8pc_1_g E869120は, セールスマンである。だから, すべての建物を$ 1 $度ずつ通って店に戻ってこなければならない。 E869120の住む街には, 建物が$ N $個あり, 道路が$ M $本ある。建物の番号は1-indexedでつけられており, 店は建物$ 1 $とする。 また, 道路 $ i $ は建物$ s_i $と建物$ t_i $を結んでいて, 距離は$ d_i $である。 しかし, その街は不審者対策として一定の時間を過ぎると道路を閉鎖する。 道路 $ i $は, E869120が出発してから時間 $ time_i $ 経つと道路が閉鎖される。 だから, その道路を通る際, 時間 $ time_i $ 以内に道路を通り終えなければならない。 そのとき, E869120は次のようなことを考えた。 「最短時間で戻ってくる方法の総数はどのくらいあるのだろう？」 そこで, 優秀なプログラマーであるあなたにプログラムを作ってもらうことになりました。 最短経路と, 最短時間で戻ってくる方法の総数を求めなさい。ただし, E869120は時間 $ 1 $ につき距離 $ 1 $ 進む。また, 道路は双方向に移動可能である。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ ・1行目には、整数$ N $ , $ M $ が与えられる。 ・次のM行には、整数$ s_i\ ,\ t_i\ ,\ d_i\ ,\ time_i $ が空白区切りで与えられる。

出力は以下の形式で標準出力に行うこと。 最短経路と, 最短時間で戻ってくる方法の総数を空白で区切って出力しなさい。 ただし, そのような経路が存在しない場合 "IMPOSSIBLE"と出力しなさい。 また,出力の末尾には改行を入れること。

### 制約 - $ 1≦N≦16 $ - $ 1≦s_i＜t_i≦N $ ※入力例ではそうとは限りません - $ 1≦d_i≦1,000,000,000,000 $ - $ 1≦time_i≦1,000,000,000,000 $ - 任意の$ i,j $に対し, $ (s_i,t_i)≠(s_j,t_j) $ ### 部分点 $ 2≦N≦8 $を満たすデータセットすべてに正解した場合は、15点が与えられる。 残りのデータセットすべてに正解した場合は、85点が与えられる。 ### Sample Explanation 1 $ 1-\ >\ 2-\ >\ 3-\ >\ 1 $ または $ 1-\ >\ 3-\ >\ 2-\ >\ 1 $ と行くと, 時間$ 6 $で行くことができる。これが最短経路である。 ### Sample Explanation 2 道路$ 1 $が時間$ 1 $経つと閉鎖されるため, $ 1-\ >\ 3-\ >\ 2-\ >\ 1 $と行くことができない。 ### Sample Explanation 3 $ 1-\ >\ 2-\ >\ 3-\ >\ 1 $ , $ 1-\ >\ 3-\ >\ 2-\ >\ 1 $と行くことはできないため, E869120は役目を果たすことができない。