*****************This code is contributed by Naimul karim*******************
#include <iostream>
 #include <vector>
 #include <utility>
 #include <algorithm>
 using namespace std;
 const int MAX = 1000;
 int id[MAX], nodes, edges;
 pair <long long, pair<int, int> > p[MAX];


 void init()
 {
     for(int i = 0;i < MAX;++i)
         id[i] = i;
 }

 int root(int x)
 {
     while(id[x] != x)  //if x is not itself parent then update its parent
     {
         id[x] = id[id[x]];
         x = id[x];
     }
     return x;
 }

 void union1(int x, int y)
 {
     int p = root(x);
     int q = root(y);
     id[p] = id[q];
 }


 long long kruskal(pair<long long, pair<int, int> > p[])
 {
     int x, y;
     long long cost, minCost = 0;
      cout<<"MST"<<endl;
     for(int i = 0;i < edges;++i)
     {
         x = p[i].second.first;
         y = p[i].second.second;
         cost = p[i].first;

         if(root(x) != root(y))
         {
             minCost += cost;

             cout<<x<<" - "<<y<<endl;//print the edges contain in spanning tree
             union1(x, y);
         }
     }
     return minCost;
 }

 int main()
 {
     int x, y;
     long long weight, cost, minCost;
     init();

     cin >> nodes >> edges;


     for(int i = 0;i < edges;++i)
     {

     cin >> x >> y >> weight;
         p[i] = make_pair(weight, make_pair(x, y));
     }


     sort(p, p + edges);
     minCost = kruskal(p);
     cout <<"Sum of edge weights  "<< minCost << endl;
     return 0;
 }

/*
 9 14
 0 1 10
 0 2 12
 1 2 9
 1 3 8
 2 4 4
 2 5 1
 3 4 7
 3 6 8
 3 7 5
 4 5 3
 5 7 6
 6 7 9
 6 8 2
 7 8 11
*/