#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// Structure to represent an edge in the graph
struct Edge {
int source, destination, weight;
};
// Function to compare edges based on their weights for sorting
bool compareEdges(const Edge& a, const Edge& b) {
return a.weight < b.weight;
}
// Function to find the parent of a vertex in a disjoint set
int findParent(int vertex, vector<int>& parent) {
if (parent[vertex] == -1)
return vertex;
return findParent(parent[vertex], parent);
}
// Function to perform union of two sets
void unionSets(int x, int y, vector<int>& parent) {
int rootX = findParent(x, parent);
int rootY = findParent(y, parent);
parent[rootX] = rootY;
}
// Function to perform Kruskal's algorithm for finding the Minimum Spanning Tree
vector<Edge> kruskalMST(vector<Edge>& edges, int numVertices) {
// Sort the edges based on their weights
sort(edges.begin(), edges.end(), compareEdges);
vector<int> parent(numVertices, -1);
vector<Edge> resultMST;
for (const Edge& edge : edges) {
int rootSource = findParent(edge.source, parent);
int rootDest = findParent(edge.destination, parent);
// Check if including this edge forms a cycle
if (rootSource != rootDest) {
resultMST.push_back(edge);
unionSets(rootSource, rootDest, parent);
}
}
return resultMST;
}
int main() {
// Number of vertices and edges in the graph
int numVertices, numEdges;
cin >> numVertices >> numEdges;
// Read the edges of the graph
vector<Edge> edges(numEdges);
for (int i = 0; i < numEdges; ++i) {
cin >> edges[i].source >> edges[i].destination >> edges[i].weight;
}
// Find and print the Minimum Spanning Tree using Kruskal's algorithm
vector<Edge> resultMST = kruskalMST(edges, numVertices);
for (const Edge& edge : resultMST) {
cout << edge.source << " " << edge.destination << " " << edge.weight << endl;
}
return 0;
}