#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxVertices 1000
#define maxEdges 1000000
int graph[maxVertices][maxVertices];
/* Input graph must be undirected,weighted and connected*/
typedef struct Edge
{
        int from,to,weight;
}Edge;
int compare(const void * x,const void * y)
{
        return (*(Edge *)x).weight - (*(Edge *)y).weight;
}
Edge E[maxEdges];
int parent[maxVertices];
void init(int vertices)
{
        int iter=0;
        for(iter=0;iter<vertices;iter++)
        {
                parent[iter]=-1;
        }

}
int Find(int vertex)
{
        if(parent[vertex]==-1)return vertex;
        return parent[vertex] = Find(parent[vertex]); /* Finding its parent as well as updating the parent 
                                                         of all vertices along this path */
}
int Union(int parent1,int parent2)
{
        /* This can be implemented in many other ways. This is one of them */
        parent[parent1] = parent2;
}
void Kruskal(int vertices,int edges)
{
        memset(graph,-1,sizeof(graph)); /* -1 represents the absence of edge between them */
        /* Sort the edges according to the weight */
        qsort(E,edges,sizeof(Edge),compare);
        /* Initialize parents of all vertices to be -1.*/
        init(vertices);
        int totalEdges = 0,edgePos=0,from,to,weight;
        Edge now;
        while(totalEdges < vertices -1)
        {
                if(edgePos==edges)
                {
                        /* Input Graph is not connected*/
                        exit(0);
                }
                now = E[edgePos++];
                from = now.from;
                to = now.to;
                weight=now.weight;
                /* See If vetices from,to are connected. If they are connected do not add this edge. */
                int parent1 = Find(from);
                int parent2 = Find(to);
                if(parent1!=parent2)
                {
                        graph[from][to] = weight;
                        Union(parent1,parent2);
                        totalEdges++;
                }
        }

}
int main()
{
        int vertices,edges;
        scanf("%d%d",&vertices,&edges);
        int iter,jter;
        int from,to,weight;
        for(iter=0;iter<edges;iter++)
        {
                scanf("%d%d%d",&from,&to,&weight);
                E[iter].from = from; 
                E[iter].to = to; 
                E[iter].weight = weight;
        }
        /* Finding MST */
        Kruskal(vertices,edges);
        /* Printing the MST */
        for(iter=0;iter<vertices;iter++)
        {
                for(jter=0;jter<vertices;jter++)
                {
                        if(graph[iter][jter]!=-1)
                        {
                                printf("Vertex %d and %d, weight %d\n",iter,jter,graph[iter][jter]);
                        }
                }
        }
        return 0;
}