#include <stdlib.h>
#include <stdio.h>

int numVertices,numEdges;
int *parent,*weight,numTrees;
int *bestEdgeNum;

struct edge {
  int tail,head,weight;
};
typedef struct edge edgeType;
edgeType *edgeTab;

int find(x)
int x;
{
int i,j,root;

for (i=x;
     parent[i]!=i;
     i=parent[i])
  ;
root=i;
/* path compression */
for (i=x;
     parent[i]!=i;
     j=parent[i],parent[i]=root,i=j)
  ;
return root;
}

void makeEquivalent(i,j)
int i,j;
{
if (weight[i]>weight[j])
{
  parent[j]=i;
  weight[i]+=weight[j];
}
else
{
  parent[i]=j;
  weight[j]+=weight[i];
}
numTrees--;
}

int main()
{
int i,MSTweight=0;
int root1,root2;
int usefulEdges;

scanf("%d %d",&numVertices,&numEdges);
edgeTab=(edgeType*) malloc(numEdges*sizeof(edgeType));
parent=(int*) malloc(numVertices*sizeof(int));
weight=(int*) malloc(numVertices*sizeof(int));
bestEdgeNum=(int*) malloc(numVertices*sizeof(int));
if (!edgeTab || !parent || !weight || !bestEdgeNum)
{
  printf("error 2\n");
  exit(0);
}
for (i=0;i<numEdges;i++)
  scanf("%d %d %d",&edgeTab[i].tail,&edgeTab[i].head,&edgeTab[i].weight);
for (i=0;i<numVertices;i++)
{
  parent[i]=i;
  weight[i]=1;
}
numTrees=numVertices;  // Each vertex is initially in its own subtree
usefulEdges=numEdges;  // An edge is useful if the two vertices are separate
while (numTrees>1 && usefulEdges>0)
{
  for (i=0;i<numVertices;i++)
    bestEdgeNum[i]=(-1);
  usefulEdges=0;
  for (i=0;i<numEdges;i++)
  {
    root1=find(edgeTab[i].tail);
    root2=find(edgeTab[i].head);
    if (root1==root2)
      printf("%d %d %d useless\n",edgeTab[i].tail,edgeTab[i].head,
        edgeTab[i].weight);
    else
    {
      usefulEdges++;
      if (bestEdgeNum[root1]==(-1)
      || edgeTab[bestEdgeNum[root1]].weight>edgeTab[i].weight)
        bestEdgeNum[root1]=i;  // Have a new best edge from this component

      if (bestEdgeNum[root2]==(-1)
      || edgeTab[bestEdgeNum[root2]].weight>edgeTab[i].weight)
        bestEdgeNum[root2]=i;  // Have a new best edge from this component
    }
  }
  for (i=0;i<numVertices;i++)
    if (bestEdgeNum[i]!=(-1))
    {
      root1=find(edgeTab[bestEdgeNum[i]].tail);
      root2=find(edgeTab[bestEdgeNum[i]].head);
      if (root1==root2)
        continue;  // This round has already connected these components.
      MSTweight+=edgeTab[bestEdgeNum[i]].weight;
      printf("%d %d %d included in MST\n",
        edgeTab[bestEdgeNum[i]].tail,edgeTab[bestEdgeNum[i]].head,
        edgeTab[bestEdgeNum[i]].weight);
      makeEquivalent(root1,root2);
    }
  printf("numTrees is %d\n",numTrees);
}
if (numTrees!=1)
  printf("MST does not exist\n");
printf("Sum of weights of spanning edges %d\n",MSTweight);
}