You cannot submit for this problem because the homework's deadline is due.

Description

Implement Kruskal and Prim's algorithm for solving the minimum spanning tree.

Format

You should use a Makefile that compiles your source file into an executeable file named "main".

Input

number of edges \(eSize\) on the first line
number of vertexes \(vSize\) on the second line
an edge in the form "\(v1\) \(v2\) \(w\)" on the following \(eSize\) line
\(v1\) and \(v2\) are the indexes (start at 0) of the two vertexes of the edge
\(w\) is the weight of the edge

Output

All the edges in the resulting minimum spanning tree
Print all the edges in the format
"\(v1\)--\(v2\)"
\(v1\) and \(v2\) are the indexes of the two vertexes of the edge, \(v1\) < \(v2\)
Print all edges in the increasing order of \(v1\), for two edges "\(v1\) \(v2\)" and
"\(v1\) \(v3\)" with \(v2\) < \(v3\), print "\(v1\) \(v2\)" first.

Sample 1

Input

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

Output

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