#include<fstream>
#include<vector>
#define M 1<<30
#define maxN 100001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muc{
    int inf,y,c;
    muc(int a,int b)
    {
        inf=a;
        c=b;
    }
    muc()
    {

    }
};
vector<muc>v[maxN];
int cost[maxN],n,m,tata[maxN];
bool viz[maxN];
void citire()
{
    int x,y,c0;
    f>>n>>m;
    for(int i=1;i<=m;i++)
        {
            f>>x>>y>>c0;
            v[x].push_back(muc(y,c0));
            v[y].push_back(muc(x,c0));
        }
}
void prim()
{
    int i,j,nodant,nod,mini,cost_total = 0;
    for(i=2;i<=n;i++)
        cost[i]=M;
    nodant=0;
    for(i=1;i<=n;i++)
    {
        mini = M;
        for(j=1;j<=n;j++)
            if(viz[j] == false && cost[j] < mini )
            {
                mini = cost[j];
                nod = j;
            }
        viz[nod] = true;
        tata[nod] = nodant;
        cost_total += cost[nod];
        nodant = nod;

        for(j=0;j<v[nod].size();j++)
        {
            muc e = v[nod][j];
            if(!viz[e.inf] && cost[e.inf] > e.c)
                cost[e.inf] = e.c;
        }

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