#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector < pair <int,int>> v[200000];
bool b[400000];
struct nod {int x,y,dist;} a[200000],sol[200000];
int cost [400000],sum;
queue <int> Q;
long long int n,k,m,nr,q;
void urc(int i)
{   int t=i/2;
    while(a[t].dist>a[i].dist&&t>0)
    {   nod c1=a[i];
        a[i]=a[t];
        a[t]=c1;
        i=t;
        t=i/2;
    }
}
void cob(int i)
{   int f1=2*i;
    int f2=2*i+1;
    int mini;
    if(a[f1].dist>a[f2].dist&&f2<=k) mini=f2;
    else mini=f1;
    while(a[i].dist>a[mini].dist&&mini<=k)
    {   nod c1=a[i];
        a[i]=a[mini];
        a[mini]=c1;
        i=mini;
        f1=2*i;
        f2=2*i+1;
        if(a[f1].dist>a[f2].dist&&f2<=k) mini=f2;
        else mini=f1;
    }

}
void ins(int x, int y, int dist)
{   a[++k].dist=dist;
    a[k].x=x;
    a[k].y=y;
    urc(k);
    cob(k);
}
void del()
{   a[1]=a[k];
    k--;
    cob(1);
}
void prim()
{   while(!Q.empty())
    {
        int k=Q.front();

        Q.pop();
        for(auto pr:v[k])
        {   int vec = pr.first;
            int cost_m = pr.second;
            ins(k,vec,cost_m);
        }
        while(b[a[1].y]==1)
        {   del();
        }
        sol[++q]=a[1];
        Q.push(a[1].y);
        sum+=a[1].dist;
        b[a[1].y]=1;
        del();
        nr++;
        if(nr==n) return;
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {   int x,y,c;
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    Q.push(1);
    b[1]=1;
    nr=1;
    prim();
    g<<sum<<'\n';
    g<<n-1<<'\n';
    for(int i=1;i<=q;i++) g<<sol[i].x<<' '<<sol[i].y<<'\n';

    return 0;
}