問題

背景

うなぎ王国の王子様は運動不足であると王様や部下たちに指摘されている．そのため，うなぎ王国の王子様はお城の近辺を散歩したいと考えており，その経路を検討している．うなぎ王国の王子様は運動を極めて嫌うため，出来るだけ短い経路が良い．しかし，うなぎ王国の王子様はうなぎであるため体がとても長く，短すぎる経路では末尾がお城から出る前に頭部がお城に戻ってきてしまい，お城から出かけたということを認めてもらえなくなるかもしれない．そこで，適度に短い散歩のための経路を知りたい．

課題

あなたの仕事は，グラフが与えられたとき頂点 $0$ を出発し頂点 $0$ へ戻る経路であって $1, 2, ..., K$ 番目に短いものの長さをそれぞれ求めるプログラムを作成することである．

グラフは単純とは限らない（即ち自己閉路や多重辺は存在し得る）． 経路中で同じ頂点を何度通っても構わない．特に，最初と最後以外で頂点 $0$ を通過してもよい． 経路は，通過した辺の列として区別される． 即ち，通過する頂点の列が等しくとも通過した辺が異なれば異なる経路とみなす． 経路の長さは通過した辺の重みの和として定義する． 本問題では，少なくとも辺を$1$本以上通過する経路のみを考える（即ち長さ $0$ の経路は除外して考える）． 長さが同じである$2$つの経路には任意に異なる順位を与えることとする． 即ち，頂点 $0$ を出発し頂点 $0$ へ戻る全ての経路を長さの昇順に並べた時の先頭 $K$ 個の経路の長さを出力せよ．

ただし，軍事機密の都合上，うなぎ王国の地図は公開されない． 従って，本日のコンテストでは，以下のように乱数を用いて生成されたグラフによりプログラムの正誤判定を行う． グラフの $M$ 本の辺は独立に生成される． 各辺について始点・終点がそれぞれ $N$ 個の頂点から一様に選択される． 各辺の重みも $1$ から $1,000,000,000$ の整数として一様に選択される． 実際には，入力はこのプログラムを用いて生成された． 擬似乱数生成器の初期化に用いられるプログラムの第四引数の値は $1$ 以上 $1,000,000$ 以下のいずれかの整数を用いた．

配点

$200$

入力

入力は以下の形式で与えられる．

$N$ $M$ $K$
$U_{1}$ $V_{1}$ $C_{1}$
$U_{2}$ $V_{2}$ $C_{2}$
...
$U_{M}$ $V_{M}$ $C_{M}$

最初の行の $N$,$M$ はグラフの頂点数，枝数を表す．$K$ は求める経路の数を表す．続く $M$ 行はグラフの辺を表す． 各 $i$ 行目は頂点 $U_{i}$,$V_{i}$ 間に重み $C_{i}$ の辺があることを表す．

制約

入力中の各変数は以下の制約を満たす．

• $N = 25,000$
• \(M = 10⁵\)
• \(K = 10⁵\)
• 入力は指定された方法によって生成されている（詳細は上記の通り）
• $0 \leq U_{i},V_{i} \lt N$

出力

出力は $K$ 行からなる．$i$ $(1 \leq i \leq K)$ 行目には $i$ 番目に短い経路の長さを出力せよ．ただし，そのような経路が存在しない場合は代わりに $-1$ を出力せよ．

入力例1Copy

3 3 5
0 1 1
1 2 1
2 0 1

入力例1に対する出力例 Copy

3
6
9
12
15

この入力は $N$,$M$,$K$ 及びグラフの生成法に関する制約を守っていないことに注意せよ． 以下に続く入力例も同様である．

入力例2Copy

2 4 5
0 0 2
0 0 3
0 1 1000
0 1 10000

入力例2に対する出力例 Copy

2
3
4
5
5

グラフは単純とは限らず，自己閉路や多重辺が存在するかもしれない．

入力例3Copy

3 3 3
0 1 1
0 2 1
1 2 1

入力例3に対する出力例 Copy

-1
-1
-1

経路の数が $i$ 個より少ない場合，$i$ 行目には $-1$ を出力する．グラフの辺は有向であることに注意せよ．