#include <fstream>
#include <queue>
#include <climits>
#include <vector>
#define nmax 200005
using namespace std;
class muchie
{
    public:
    int u,v,cost;
    bool operator()(const muchie &p1, const muchie &p2)
    {
        return p1.cost>p2.cost;
    }
    muchie(int a=0,int b=0,int c=0): u(a),v(b),cost(c){}
};
vector <muchie> a[nmax];
vector <muchie> alese;
priority_queue <muchie, vector <muchie>, muchie> q;
bool viz[nmax];
int ct;
void solve()
{
    muchie x,y;
    unsigned int i;
    while (!q.empty())
    {
        x=q.top();
        q.pop();
        if ((!viz[x.u]))
        {
            viz[x.u]=true;
            ct+=x.cost;
            for (i=0;i<a[x.u].size();i++)
            {
                y=a[x.u][i];
                y.v=x.u;
                if(!viz[y.u])
                    q.push(y);
            }
            alese.push_back(muchie(x.u,x.v,0));
        }
    }
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int x,y,c;
    unsigned int i,n,m;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        a[x].push_back(muchie(y,0,c));
        a[y].push_back(muchie(x,0,c));
    }
    q.push(muchie(1,0,0));
    solve();
    fout<<ct<<'\n';
    fout<<alese.size()-1<<'\n';
    for (i=1;i<alese.size();i++)
    {
        fout<<alese[i].u<<' '<<alese[i].v<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}