Problem E: Poor Mail Forwarding
Masa 君が住んでいる地域の郵便システムは少々変わっている。 この地域では、各々の郵便局に対して 1 から順に連続した異なる番号がつけられており、ある郵便局に届けられた郵便物は、その郵便局からいくつかの郵便局を経由して目的の郵便局に届けられる。 郵便物の「転送」は、特定の郵便局の間でしか行われない。 ただし、転送が行われる郵便局同士の間では、転送は双方向に行われる。
ある郵便局から宛先まで郵便物を転送するための経路が複数存在する場合は、 宛先までの距離が最短となるような経路を使用する。 したがって、転送先はそのような最短経路における次の郵便局となる。 もし、総距離が最短となる経路が複数存在する場合は、直接の転送先となる郵便局の番号が若いほうに転送する。
ところで、この地域では深刻な労働力不足に悩まされており、郵便局間の転送を行う転送員が各郵便局に 1 人ずつしかいない。 彼らががんばって往復しているのである。 当然、ある郵便局に郵便物が届いた時点でその郵便局に所属する転送員が出払っていた場合は、その郵便局からの転送は一時的にストップする。
彼らは自分の所属する郵便局にいるときに、その郵便局から転送されていない郵便物が存在すれば即座に出発し、転送先に届けた後は即座に戻ってくる。 彼が転送先の郵便局から帰ってくるとき、彼の郵便局に転送される郵便物がその郵便局にあったとしても、それを運んでくることはしない (その郵便物の転送はその郵便局の転送員の仕事である)。
転送する際に、複数の郵便物が溜まっていた場合は、その郵便局に最も早く届けられた郵便物から転送を行う。 ここで、同じ時刻に届いた郵便物が複数あったときは、直接の転送先となる郵便局の番号が若いほうから転送する。 なお、同じ転送先となる郵便物があればそれも一緒に転送する。 また、転送員の出発時刻と同じ時刻に、同じ郵便局に転送されるべき郵便物が到着した場合は、それも一緒に転送される。 なお、彼らは全員、距離 1 の移動に時間 1 を要する。
あなたには、郵便局間の転送に関わる情報と、各郵便局に郵便物が届いた時刻のリストが与えられる。 このとき、郵便物の動きをシミュレートし、各郵便物が宛先の郵便局に届いた時刻を報告せよ。 問題のシミュレーション中で必要となる時刻はすべて 0 以上 231 未満の範囲におさまると仮定してよい。
Input
入力は複数のデータセットからなり、入力の終了は 0 0 とだけ書かれた 1 行で表される。 それぞれのデータセットの書式は以下の通りである。
データセットの最初の行には、整数 n (2 <= n <= 32) と m (1 <= m <= 496) が 1 文字のスペースで区切られて順に与えられる。 n は郵便局の総数を、m は郵便局間の直接の転送経路の数を表す。 ある 2 つの郵便局間に 2 つ以上の直接転送経路が存在することはない。
続く m 行に、局間の直接転送経路の情報を記した 3 つの整数が書かれる。 1 つ目と 2 つ目が転送経路の両端の郵便局の番号 (1 以上 n 以下) であり、最後の整数がその 2 局間の距離を表す。 距離は 1 以上 10000 未満である。
次の行には、処理すべき郵便物の数を表す整数 l (1 <= l <= 1000) が書かれ、 それに続く l 行に各郵便物の詳細が書かれる。 その各行の先頭には 3 つの整数が書かれている。 これらは順に、発送元の郵便局の番号、宛先の郵便局の番号、発送元の郵便局に届いた時刻である。 行の最後に、郵便物のラベルを表す文字列が書かれる。 このラベルは、長さが 1 文字以上 50 文字以内であり、 アルファベット、数字、ハイフン ('-')、アンダースコア ('_') のみからなる。 これらの各郵便物の情報は、発送元の郵便局に到着した時刻順に書かれている。 同じ時刻のときは、順番は特に規定されていない。 また、同じラベルの郵便物や、発送元と宛先が同じ郵便物または配達するための経路が存在しない郵便物は存在しない。
入力行中の各数値や文字列の区切りは、全て 1 文字のスペースである。
Output
各々のデータセットに対して l 行の出力を行う。 それぞれの出力は、以下の書式に従う。
各々の郵便物について、その郵便物が届いた時刻を 1 行に出力する。その行には、最初に郵便物のラベルを出力し、次に 1 文字のスペースを挟んで、最後に郵便物が宛先の郵便局に到着した時刻を出力する。 これらは到着時刻順に出力する。同時刻に到着した郵便物が複数ある場合は、そのラベルの ASCII コードの昇順に出力する。
各々のデータセットに対応する出力の間に、空行が 1 つ挿入される。
Sample Input
4 5 1 2 10 1 3 15 2 3 5 2 4 3 3 4 10 2 1 4 10 LoveLetter 2 3 20 Greetings 3 3 1 2 1 2 3 1 3 1 1 3 1 2 1 BusinessMailC 2 3 1 BusinessMailB 3 1 1 BusinessMailA 0 0
Output for the Sample Input
Greetings 25 LoveLetter 33 BusinessMailA 2 BusinessMailB 2 BusinessMailC 2