Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.
Submit All submissions Best solutions PDF Back to list

EISMLEDG - Question 2

You are given an undirected graph that has n vertices and m edges. You should output the list of edges in lexicographic order. Note that if there is more than one edge between two vertices, you should output the smallest weight edge only.

 

Input

The first line contains two integers n, m (0 < n, m ≤ 105).

Each of the next m lines contains three integers a, b, c representing an edge that connects vertex a and vertex b and has weight c (0 ≤ a, b < n , 0 < c < 109 ).

Output

The required list of edges.

Sample

https://drive.google.com/file/d/1Lsjs30v16V6l3yGzheGBbQ-MRIY4QBK4/view?usp=sharing

Input

Output

5 6

0 1 1

1 2 2

2 3 5

0 3 3

2 1 1

3 0 1

0 1 1

0 3 1

1 2 1

2 3 5
Submit solution!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.