You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

马上放暑假了, 小北打算在省内玩一下.

山东省 有 $n$ 个城市，由 $m$ 条双向道路连接。每条道路 $(u_i, v_i, w_i)$ 表示连接着两个城市 $u_i, v_i$，从 $u_i$ 到 $v_i$ 或 $v_i$ 到 $u_i$ 都有 $w_i$ 的路程。

假设 小北 住在城市 $x$，他周末想要出游，但是太远的城市他会不愿意去，所以 小北 想知道距离城市 $x$ 最近的 $k$ 个城市的是哪些（不包含城市 $i$ 本身）。由于有可能有相同距离的城市，你只需要告诉 小北 这些城市的距离就好。

现在，你需要对 $x = 1, 2, \dots, n$ 都得到答案，保证图连通。

输入格式

第一行三个正整数 $n, m, k$，表示城市数，道路数，和题目中的 $k$。

下面 $m$ 行，每行三个正整数 $(u, v, w)$ 表示一条边。

输出格式

一共 $n$ 行，每行 $k$ 个正整数，从小到大排序，第 $i$ 行表示距离城市 $i$ 最近的几个城市的距离是多少。

4 5 3
1 2 10
2 4 3
3 4 4
2 3 5
1 3 8

8 10 12
3 5 10
4 5 8
3 4 12

数据范围与约定

对于所有数据，有 $1 \leq k < n \leq 10^5;k < 16; w_i \leq 10^4;n - 1 \leq m \leq 10^6$，保证图连通，保证没有重边，保证没有自环。

对于 $30\%$ 的数据，有 $n \leq 500$。

对于另外 $30\%$ 的数据，有 $n, m \leq 3000$。

对于另外 $10\%$ 的数据，有 $k = 1$。

对于 $100\%$ 的数据，没有其他限制。