/// Algoritmul lui Prim

#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int N = 200010;
int n,m,COST;
vector<pair<int,int>> v[N],sol;
priority_queue<tuple<int,int,int>> q;
bitset<N> used;
int main()
{
    f>>n>>m;
    for(;m;m--)
    {
        int x,y,cst;
        f>>x>>y>>cst;
        v[x].push_back(make_pair(y,cst));
        v[y].push_back(make_pair(x,cst));
    }
    used[1]=1;
    for(auto it:v[1])
    {
        int vec,cst;
        tie(vec,cst)=it;
        q.push(make_tuple(-cst,1,vec));
    }
    while(q.size())
    {
        int cst,x,y;
        tie(cst,x,y)=q.top();q.pop();
        if(used[x]&&used[y])
            continue;
        sol.push_back(make_pair(x,y));
        COST-=cst;
        if(used[x])
            x=y;
        used[x]=1;
        for(auto it:v[x])
        {
            tie(y,cst)=it;
            if(!used[y])
                q.push(make_tuple(-cst,x,y));
        }
    }
    g<<COST<<'\n'<<n-1<<'\n';
    for(auto it:sol)
        g<<it.first<<' '<<it.second<<'\n';
    return 0;
}