#include<fstream>
#include<queue>
#include<vector>
#define M 2000000000
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int cost[100001],tata[100001],n,m,i,j,sum,nodcur;
bool viz[100001];
struct nod
{
    int inf,c;
};
vector<nod> L[100001];
struct cmp
{
    bool operator()(nod a,nod b)
    {
        if(cost[a.inf]>cost[b.inf])return true;
        else return false;
    }
};
priority_queue<nod,vector<nod>,cmp>heap;
void citire()
{
    int x1,y1,z1;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x1>>y1>>z1;
        nod a;
        a.inf=y1;
        a.c=z1;
        L[x1].push_back(a);
        a.inf=x1;
        L[y1].push_back(a);
    }
}
void preparare(int i)
{
    for(j=0;j<L[i].size();j++)
        if(viz[L[i][j].inf]==false)
            if(L[i][j].c<cost[L[i][j].inf])
        {
            cost[L[i][j].inf]=L[i][j].c;tata[L[i][j].inf]=i;
            heap.push(L[i][j]);
        }
}
void prim()
{
    for(i=2;i<=n;i++)
        cost[i]=M;
    viz[1]=true;
    preparare(1);

    for(i=1;i<n;i++)
    {
        nodcur=heap.top().inf;
       // sum+=heap.top().c;
        heap.pop();
        viz[nodcur]=true;
        preparare(nodcur);
    }
    for(i=1;i<=n;i++)
            sum+=cost[i];
    g<<sum<<'\n'<<n-1<<'\n';
    for(i=2;i<=n;i++)
        g<<tata[i]<<" "<<i<<'\n';
}
int main()
{
    citire();
    prim();

    return 0;
}