#include <iostream>
#include <fstream>
#define inf 1000000000
#define maxn 23170
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int n,m,a[maxn][maxn],t[maxn],s[maxn];

void citire(int &n, int &m)
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)
            a[i][j]=inf;
    int x,y,c;
    for(int i=1;i<=m;i++)
        {
            f>>x>>y>>c;
            a[x][y]=a[y][x]=c;
        }
}
int cauta_nod(int &nod)
{
    int mn=inf;
    for(int i=1;i<=n;i++)
    if(s[i]!=0 && a[i][s[i]]<mn)
        {
            mn=a[i][s[i]];
            nod=i;
        }
    return mn;
}
void actualizeaza(int nod)
{
    for(int i=1;i<=n;i++)
    if(s[i]!=0 && a[i][s[i]]>a[i][nod])
            s[i]=nod;
}
int main()
{
    int v=1;
    citire(n,m);
    s[v]=0;
    for(int i=1;i<=n;i++)
      if(i!=v)
         s[i]=v;
    int nod,mn,cost=0;
    for(int k=1;k<=n-1;k++)
       {
            mn=cauta_nod(nod);
            t[nod]=s[nod];
            cost=cost+mn;
            s[nod]=0;
            actualizeaza(nod);
       }
    g<<cost<<'\n'<<n-1<<'\n';
    for(int i=1;i<=n;i++)
        if(t[i]!=0)
        g<<t[i]<<" "<<i<<'\n';
}