#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
#define dim 200005
#define INF 1002
int n,m;
vector<pair <int,int> > v[dim];
vector<int> d;
vector<pair<int,int>> q;
struct muchie
{
    int x,y,c;
};
bool fr[dim];

///Prim
int main()
{
    int i,j,mini,x,y,c,s=0;
    fin>>n>>m;
    d.resize(n+1);
    for(i=0;i<n+1;i++)
        d[i]=INF;
    for(i=0;i<m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    d[1]=0;
    for(i=1;i<=n;i++)
    {
        mini=-1;
        for(j=1;j<=n;j++)
        {
            if(fr[j]==0 && (mini==-1 || d[mini]>d[j]))
                mini=j;
        }
        fr[mini]=1;
        s+=d[mini];
        q.push_back(make_pair(i,mini));
        for(auto k:v[mini])
        {
            if(k.second<d[k.first])
                d[k.first]=k.second;
        }
    }
    fout<<s<<'\n'<<n-1<<'\n';
    for(auto k:q)
    {
        fout<<k.first<<" "<<k.second<<'\n';
    }
    return 0;
}