#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,x,y,c,d[200001],cost,fr[200001],tata[200001];
struct numar
{
    int nod,c;
};
vector <numar> A[200001];
struct cmp
{
    bool operator() (const numar& a,const numar& b)
    {
        return a.c>b.c;
    }
};

priority_queue <numar,vector <numar>,cmp> q;
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        A[x].push_back({y,c});
        A[y].push_back({x,c});
    }
    for(int i=1;i<=n;i++)
        d[i]=100001;
    q.push({1,0});
    int ult=1;
    for(int i=2;i<=n+1;i++)
    {

       while(fr[q.top().nod]==1)
        q.pop();
        int x=q.top().nod;
        tata[x]=ult;
        int c2=q.top().c;
        fr[x]=1;

        q.pop();
        for(auto i:A[x])
        {

            if(d[i.nod]>i.c && fr[i.nod]==0)
            {
                d[i.nod]=i.c;
                q.push({i.nod,i.c});
            }
        }
        cost+=c2;
        ult=x;


    }
    fout<<cost<<"\n";
    fout<<n-1<<"\n";
    for(int i=2;i<=n;i++)
        fout<<tata[i]<<" "<<i<<"\n";
    return 0;
}