F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 1267. -- Kth Number I

1267: Kth Number I

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 453  Solved: 109
[Submit][Status][Discuss]

Description


给出1棵N个节点的树,每条边上有一条权值,对于所有不同的点对(u,v u<v)之间的路径按长度进行排序。要求输出前M长的路径长度。


Input


第一行有2个整数N,M,接下来N-1行每行有3个整数u,v,w(1<=u,v<=N,0<=w<=32767)代表了顶点u和v之间有一条长度为w的边


Output

输出M行,第i行输出第i长的路径长度


Sample Input

4 3

1 2 0

2 3 4

2 4 5

Sample Output

9

5

5

HINT

 对于20%的数据,有N<=1000


对于50%的数据,有N<=10000

对于100%的数据,有N<=50000,M<=min(N*(N-1)/2,300000)

Source

By abs

[Submit][Status][Discuss]

HOME Back