#include <fstream>
#include <vector>
#include <queue>
#define dim 105
#define inf 0x3f3f3f3f
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

int n,m,cost_total;
int v[dim],t[dim],d[dim];
vector<pair<int,int>>V[dim];
vector<int>Arbore;

priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;//cost,nod

void prim(){
    t[1]=-1;
    for(int i=2;i<=n;++i) d[i]=inf;
    
    Q.push({0,1});
    
    while(!Q.empty()){
        auto cap=Q.top();
        
        int nod=cap.second;
        int cost=cap.first;
        
        if(v[nod]){
            Q.pop();
            continue;
        }
        
        v[nod]=1;
        cost_total+=cost;
        Arbore.push_back(nod);
        
        
        for(auto nbr:V[nod]){
            int vec=nbr.first;
            int cst=nbr.second;
            if(!v[vec] && d[vec]>cst){
                d[vec]=cst;
                t[vec]=nod;
                Q.push({cst,vec});
            }
        }
    }
    
}

int main()
{
    cin>>n>>m;
    int a,b,c;
    for(;m;--m){
        cin>>a>>b>>c;
        V[a].push_back({b,c});
        V[b].push_back({a,c});
    }
    
    prim();
    cout<<cost_total<<'\n'<<n-1<<'\n';
    for(auto val:Arbore) if(t[val]!=-1) cout<<val<<" "<<t[val]<<'\n';
    return 0;
}