#include <fstream>
#include <vector>
#include <queue>
#define pii pair<int,int>
#define dim 200002
#define inf 0x3f3f3f3f

using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

int n,m,cost_tot;
int d[dim],t[dim],v[dim];
vector<pii>V[dim];
vector<int>Arbore;
priority_queue<pii,vector<pii>,greater<pii>>Q;

void prim(){
    t[1]=-1;
    for(int i=2;i<=n;++i) d[i]=inf;
    
    Q.push({0,1});
    while(!Q.empty()){
        int cst=Q.top().first;
        int nod=Q.top().second;
        
        if(v[nod]){
            Q.pop();
            continue;
        }
        
        Arbore.push_back(nod);
        v[nod]=1;
        cost_tot+=cst;
        
        for(auto x:V[nod]){
            int cost=x.second;
            int vec=x.first;
            
            if(d[vec]>cost && !v[vec]){
                d[vec]=cost;
                t[vec]=nod;
                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<<cost_tot<<'\n'<<n-1<<'\n';
    
    for(auto val:Arbore) if(t[val]!=-1) cout<<val<<" "<<t[val]<<'\n';
    
    return 0;
}