///********This code is contributed By Naimul Karim Hredoy************
#include<bits/stdc++.h>
using namespace std;

int v;
int parent[50];
int adjMat[50][50];
int MST[50][50];

int parentOf(int n){
    int q = n;
    int p = parent[n];
    while(p!=-1){
        p=parent[p];
        n=parent[n];
    }

    // path compression
    while(parent[q]!=-1){
        parent[q] = n;
        q = parent[q];
    }

    return n;
}

void kruskal(){
    for(int i=0;i<v;i++)
    {
        parent[i]=-1;
    }
    set<int> s;
    while(s.size()<v){
        int u,vr, m=INT_MAX;
        for(int i=0;i<v;i++){ // minimum edge is [u][v]
            for(int j=0;j<v;j++){
                if( adjMat[i][j]!=0 && m>adjMat[i][j]){
                    m=adjMat[i][j];
                    u=i; vr=j;
                }
            }
        }

        adjMat[u][vr]=0;
        adjMat[vr][u]=0;
        if(parentOf(u)!=parentOf(vr) ){
            parent[parentOf(u)]=parentOf(vr);
            MST[u][vr]=m;
            MST[vr][u]=m;
            s.insert(u);
            s.insert(vr);
        }
    }
}

int main(){

    int e;
    cin >> v >> e;

    for(int i=0; i<v; i++){
        for(int j=0; j<v; j++){
            adjMat[i][j] = 0;
            MST[i][j] = 0;
        }
    }


    for(int i=0; i<e;i++){
        int x,y,z;
        cin >>x>>y>>z;
        adjMat[x][y] = z;
        adjMat[y][x] = z;
    }

    kruskal();

  /*  cout <<"\nPARENTS-\n";
    for(int i=0;i<v;i++){
        cout<< i <<" | ";
    }
    cout<<endl;
    for(int i=0;i<v;i++){
        cout<< parent[i] <<" | ";
    }
    cout <<endl;*/

    int sum = 0;
    cout << "MST\n";
    for(int i=0;i<v;i++){
        for(int j=0;j<i;j++){
            if(MST[i][j]!=0){
                cout << i << " - " << j <<endl;
                sum+=MST[i][j];
            }
        }
    }
    cout <<endl;

    cout << "Sum of edge weights "<< sum<<endl;

    return 0;
}
/*
 4 5
 0 1 10
 0 2 6
 0 3 5
 1 3 15
 2 3 4
*/