#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<set>
#include<list>
#include<string>
#include<queue>
using namespace std;
vector<int>pset(100);
vector< pair<int,int> >disjoint_set;
void init_set(int n)
{
  for(int i=1;i<=n;i++)
     pset[i]=i;
}
int find_set(int i)
{
    return (pset[i]==i)? i: (pset[i]=find_set(pset[i]));
}
bool is_same_set(int i,int j)
{
  return (find_set(i)==find_set(j));
}
void union_set(int i,int j)
{
  int u=find_set(i);int v=find_set(j);
  pset[u]=v;
  //cout<<u<<" "<<v<<endl;
  disjoint_set.push_back(make_pair(i,j));
}
int main()
{
   freopen("c:\\temp\\in.txt","r",stdin);
    priority_queue< pair<int,pair<int,int> > > my_graph;
    int vertics,edges;
    printf("Enter the number of vertics and edges: ");
     cin>>vertics>>edges;
     printf("Enter the edges: \n");
     for(int i=1;i<=edges;i++)
     {
       int u,v,w;
       cin>>u>>v>>w;
              my_graph.push(make_pair(-w,(make_pair(u,v))));
     }
  init_set(vertics);
  int total=0;
  while(!my_graph.empty())
     {
        pair<int, pair<int,int> >fron=my_graph.top();
        my_graph.pop();
         int u=fron.second.first;
         int v=fron.second.second;
         int check=is_same_set(u,v);
         //cout<<"find"<<endl;
         if(!check)
         {
             total=total-fron.first;
            union_set(u,v);
             //printf("fff %d %d\n",u,v);
         }

     }
     for(vector< pair<int,int> >:: iterator it=disjoint_set.begin();it!=disjoint_set.end();it++)
     {
         cout<<it->first<<" "<<it->second;
         cout<<endl;
     }
     cout<<"The minimum weight is: ";
     cout<<total<<endl;
 return 0;
}