#include <bits/stdc++.h>
using namespace std;

int cmin[200005],ocupat[200005],p[200005],g[20005][20005];
//vector <int> g[1005];
int n,m,nr,valoare,varf;

void citire()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        g[i][j]=10000;
    for (int i=1;i<=m;i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        g[x][y]=c;
        g[y][x]=c;
    }
    for (int i=1;i<=n;i++)
    {
        cmin[i]=g[1][i];
        p[i]=1;
        ocupat[i]=1;
    }
    ocupat[1]=0;
    p[1]=0;
    nr=n-1;
}

void afisare()
{
    int cost=0;
    for (int i=2;i<=n;i++)
        cost+=g[i][p[i]];
    cout<<cost<<'\n';
    cout<<n-1<<'\n';

    for (int i=2;i<=n;i++)
        cout<<p[i]<<' '<<i<<'\n';
}
int main() {
citire();
while (nr)
{
    valoare=10000;
    for (int i=1;i<=n;i++)
        if (ocupat[i] && valoare>cmin[i])
    {
        valoare=cmin[i];
        varf=i;
    }
    ocupat[varf]=0;
    nr--;
    for (int i=1;i<=n;i++)
        if (ocupat[i] && g[i][varf]<cmin[i])
    {
        p[i]=varf;
        cmin[i]=g[i][varf];
    }
}
afisare();

    return 0;
}