该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“赛后递交”以递交本题。

题目描述

小 Z 作为游击队长，要长期和敌军周旋。

小 Z 所在的战场可以看作由 $n$ 个点，$m$ 条边组成的地图。边都是双向的，但这些边的修建都需要相应的代价 $w_i$。

为了组织进攻，需要以最小的代价修路将所有的城市调动起来，即让 $n$ 个城市互相连通。但是敌军也非常狡猾，一旦道路修建完毕之后，他们就会彻底摧毁当天所有的道路（这些道路无法再重新修建）。第二天小 Z 又要重新组织相应的道路修建，以满足所有城市联动并且花费最小的需求，相应的，敌军会再次彻底摧毁第二天修建的所有道路，小 Z 继续组织第三天的修路工作....直到拖延 $k$ 天，等待援军的来临。

小 Z 作为队长，需要未雨绸缪的计算出每条道路会在哪一天进行修建。

输入格式

第一行，$3$ 个正整数 $n,m,k$，表示城市的总数量，待修建道路的总数量，战争的天数。

接下来 $m$ 行，每行 $3$ 个正整数 $u_i,v_i,w_i$，表示 $u_i$ 城市与 $v_i$ 城市之间有一条花费为 $w_i$ 的待修建道路。

输出格式

$m$ 行，每行一个数字，表示第 $i$ 条道路会在哪一天被修建；如果这条道路一直都不会被修建则输出 -1。

输入输出样例

3 5 2
1 2 3
1 2 1
2 3 4
2 3 6
1 3 2

2
1
2
-1
1

样例 $\tt \#1$说明

• 给定的道路中，第 $2,5$ 条道路会在第一天被修建，花费的代价最小为 $1+2=3$，$3$ 个城市都会被联通，之后这两条道路就会被摧毁；第二天继续选择第 $1,3$ 条道路，花费代价最小为 $3+4=7$；第 $4$ 条道路不会被修建，因为一共只有 $2$ 天。

3 5 4
1 2 3
1 2 1
2 3 4
2 3 6
1 3 2

2
1
2
3
1

样例 $\tt \#2$说明

• 前 $2$ 天的情况与样例一相同，注意第 $3$ 天虽然只剩第 $4$ 条道路了，无论当天能否联通，依旧会选择修建。

3 5 4
2 3 3
1 2 1
2 3 4
2 3 6
1 3 2

2
1
3
4
1

样例 $\tt \#3$说明

• 第 $1$ 天的情况与样例一相同，注意第 $2$ 天开始已经无法修建道路使得所有城市联通了，但依旧会选择修建 $1$ 号道路；第 $3$ 天也已经无法修建道路使得所有城市联通了，但依旧会选择修建 $3$ 号道路；第 $4$ 天已经无法修建道路使得所有城市联通了，但依旧会选择修建 $4$ 号道路。

数据范围

• 对于 $30\%$ 的数据，$m\le10^3$
• 对于 $100\%$ 的数据，$1\le n\le 5\times10^3,1\le k\le 10^4,0\le m\le 3\times10^5,1\le u_i,v_i\le n,1\le w_i\le 10^9$
• 保证没有自环，但可能会有重边，所有的 $w_i$ 各不相同