/ 
Time Limit: 5 sec / Memory Limit: 256 MB
問題文
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点が与えられる。
入力例1
3 3 1 2 1 6 2 3 2 6 3 1 3 6
出力例1
6 2
1->2->3->1 または 1->3->2->1 と行くと, 時間6で行くことができる。これが最短経路である。
入力例2
3 3 1 2 1 1 2 3 1 3 3 1 1 3
出力例2
3 1
道路1が時間1経つと閉鎖されるため, 1->3->2->1と行くことができない。
入力例3
3 3 1 2 1 1 2 3 1 1 3 1 1 1
出力例3
IMPOSSIBLE
1->2->3->1 , 1->3->2->1と行くことはできないため, E869120は役目を果たすことができない。
入力例4
3 2 1 2 3 20 2 3 2 20
出力例4
IMPOSSIBLE