该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Once again, the elves successfully defeated the guards and proudly invaded Gaus with 2.58 million elves. So Gauss the Great had to take effective measures.

小精灵又一次成功击败护卫队，骄傲地带着2580000名小精灵入侵高斯国。所以高斯大帝不得不采取有效措施。

Description

There are a total of n cities in Gosse country, and some cities are connected with each other by roads. Now there is a war in Gosse country, and every road has a dangerous value ki. As an agent of the Goss, you need to be able to observe the situation in each city at any time, so you have installed a armor with a defense value of C for each intelligence soldier, which means that you can move freely between all roads with a danger value less than C .. However, armor with higher defense value means higher cost. Small X wants to know, if there are currently a total of T intelligence soldiers, you can randomly distribute the T soldiers at any position in N cities at the beginning, then at least what armor with defense value is needed to enable soldiers to reach every city on the map. You need to output the answer to every integer in 1≤t<n

高斯国中共有 n 个城市，且一些城市与城市之间有无向道路联通，现在高斯国发生了战争，每条道路都有一个危险值ki。
你身为 高斯国的情报员，需要随时能够观测到每个城市的情况，因此你给每个情报士兵都安装了一个防御值为 c 的铠甲，这意味着你们可以在所有危险值小于 c的道路之间任意穿梭。
但是防御值越高的铠甲，意味着成本越高，小 X 想知道，如果现在一共有 t 个情报士兵，开始时你可以把这 t 个士兵任意分布在 n 个城市中的任意位置，那么至少需要防御值为多少的铠甲，才能够让地图上每一个城市都能够有士兵可以到达。
你需要对1≤t<n 中的每一个整数都输出答案，保证图是联通的。

Format

Input

A total of m+1 rows, the first two integers represent n, m. After m rows, each row is given u, v, w, which means there is an undirected edge with length w between u and v.

共m+1行，第一行2个整数表示n，m。
之后m行，每行给定u，v，w，表示u和v之间有一条长度为w的无向边。

Output

A total of n-1 lines, line I represents the answer when t = I.

共n-1行，第i行表示t=i时的答案。

Sample 1

Input

3 3
1 2 1
2 3 2
1 3 3

Output

3
2

Limitation

对于40%的数据，2≤n,m≤10；
对于100%的数据，2≤n,m≤10^6，输入数据中所有的数字均为 [0,10^6]间的整数。

Source

Amorphophallus Orz Group