Module: ダイクストラのアルゴリズム

Problem

負でないエッジ長を持つ無向重み付きグラフ内の、指定された頂点から他のすべての頂点までの距離を求めるプログラムを作成します。このプログラムは、大規模な疎グラフに対して高速である必要があります。

入力

入力の最初の行には数値 NUM が含まれています。ダイクストラのアルゴリズムの異なる実行の数 (異なるグラフ上で)。これに NUM 個のブロックが続き、それぞれのブロックは次の構造になっています。

ブロックの最初の行には、スペースで区切られた 2 つの数値NとMが含まれています。グラフの頂点の数と辺の数。これにM行が続き、各行にはスペースで区切られた 3 つの整数が含まれます。最初の 2 つはそれぞれ 0 ～N–1 の範囲で、対応するエッジの端を表します。 0 ～ 20000 の範囲で、このエッジの長さを示します。さらに、ブロックの最後の行には、0 から  N–1 までの 1 つの数値が入力されます。ピーク、検索する必要がある距離。

1 つのテスト内の異なるグラフの数 NUM は 5 を超えません。頂点の数は 60000 を超えず、エッジは 60000 を超えません。 200000.

インプリント

NUM 行を標準出力 (画面) に出力します。各行にはスペースで区切られたN_i 数値が含まれます。重み付き無向グラフの指定された開始頂点からその 0 番目、1 番目、2 番目などまでの距離。頂点 (最後の数字の後に追加のスペースが許可されます)。指定された最初の頂点から到達できない頂点がある場合は、距離の代わりに数値 2009000999 を出力します (実際の距離はすべてこれより小さいことが保証されます)。

例