#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;
};
struct numar2
{
    int nod,c,tata;
};
vector <numar> A[200001];
struct cmp
{
    bool operator() (const numar2& a,const numar2& b)
    {
        return a.c>b.c;
    }
};

priority_queue <numar2,vector <numar2>,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,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]=q.top().tata;

        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;
                //tata[i.nod]=x;
                q.push({i.nod,i.c,x});
            }
        }
        cost+=c2;



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