// Prim - incepe de la un nod si cauta cea mai ieftina muchie care trece spre alt nod
#include<bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
#define cin fin
#define cout fout
int n,m,c[20005][20005],d[400005],t[400005];
bool v[400005];

int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            c[i][j]=1e9;

    for(int i=1; i<=m; i++)
    {
        int a,b,x;
        cin>>a>>b>>x;
        c[a][b]=c[b][a]=min(c[a][b],x);
    }

    for(int i=2; i<=n; i++)
        d[i]=1e9;
    t[1]=0;
    d[1]=0;
    long long sol=0;

    for(int i=1; i<=n; i++)
    {
        int u=-1;
        for(int j=1; j<=n; j++)
            if(!v[j]&&(u==-1||d[j]<d[u]))u=j;

        v[u]=1;
        sol+=d[u];

        for(int j=1; j<=n; j++)
        {
            if(!v[j]&&c[u][j]<d[j])
            {
                d[j]=c[u][j];
                t[j]=u;
            }
        }
    }

    cout<<sol<<'\n';
    for(int i=2; i<=n; i++)
        cout<<t[i]<<' '<<i<<'\n';
}