G - Revenge of Traveling Salesman Problem

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