#include<fstream>
#include<vector>
#include<queue>
#define maxN 200001
#define maxm 400001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct nod{
    int inf,c;
};
struct coord{
    int x,y,co;
};
struct cmp{
    bool operator() ( coord a, coord b)
    {
        return a.co>b.co;
    }
};
vector<nod>v[maxN];
priority_queue<coord,vector<coord>,cmp>heap;
int n,m,tata[maxN],sol;
bool viz[maxN];
void citire()
{
    int i,q,p,r;
    nod a;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>q>>p>>r;
        a.c=r;
        a.inf=p;v[q].push_back(a);
        a.inf=q;v[p].push_back(a);
    }
}
void proceseaza(int nod_start)
{
    int i;
    for(i=0;i<v[nod_start].size();i++)
        {
            if(viz[v[nod_start][i].inf]==false)
                {
                    coord a;
                    a.x=nod_start;
                    a.y=i;
                    a.co=v[nod_start][i].c;
                    heap.push(a);
                }
        }
}
void prim()
{
    int i,j,k;
    coord a;
    proceseaza(1);
    viz[1]=true;
    for(k=1;k<n;k++)
    {
        a=heap.top();
        i=a.x;
        j=a.y;
        while(viz[v[i][j].inf]==true)
        {
           heap.pop();
            a=heap.top();
            i=a.x;
            j=a.y;
        }
        if(!heap.empty())
        {


        heap.pop();


        tata[v[i][j].inf]=i;
        sol+=a.co;
        viz[v[i][j].inf]=true;
        proceseaza(v[i][j].inf);
        }

    }
}
void afisare()
{
     g<<sol<<'\n'<<n-1<<'\n';
    for(int i=2;i<=n;i++)
        g<<i<<" "<<tata[i]<<'\n';
}
int main()
{
    citire();
    prim();
    afisare();
    return 0;
}