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

int n,m,ctot;
int d[200002],t[200002],incoada[200002];
vector<pii>V[200002],arb;
priority_queue<pii,vector<pii>,greater<pii>>Q;

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

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int a,b,c;
        cin>>a>>b>>c;
        V[a].push_back({b,c});
        V[b].push_back({a,c});
    }
    
    prim();
    
    cout<<ctot<<'\n'<<n-1<<'\n';
    for(auto muchie:arb)
       if(muchie.first!=0) cout<<muchie.first<<" "<<muchie.second<<'\n';
    
    return 0;
}