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

ifstream fin("apm.in");
ofstream fout("apm.out");

#define cin fin
#define cout fout

struct muchie
{
    int a,b,c;
};

const int nmax=200005,mmax=400005;

muchie m[mmax];
int t[nmax],r[nmax],best[nmax];
int sola[nmax],solb[nmax];

int rad(int x)
{
    if(t[x]==x)return x;
    return t[x]=rad(t[x]);
}

void unire(int a,int b)
{
    a=rad(a);
    b=rad(b);

    if(a==b)return;

    if(r[a]<r[b])t[a]=b;
    else if(r[b]<r[a])t[b]=a;
    else
    {
        t[b]=a;
        r[a]++;
    }
}

int main()
{
    int n,mr;
    cin>>n>>mr;

    for(int i=1; i<=mr; i++)
        cin>>m[i].a>>m[i].b>>m[i].c;

    for(int i=1; i<=n; i++)
        t[i]=i;

    long long cost=0;
    int nr=0;
    int comp=n;

    while(comp>1)
    {

        for(int i=1; i<=n; i++)
            best[i]=-1;

        for(int i=1; i<=mr; i++)
        {
            int a=rad(m[i].a);
            int b=rad(m[i].b);

            if(a==b)continue;

            if(best[a]==-1||m[i].c<m[best[a]].c)
                best[a]=i;

            if(best[b]==-1||m[i].c<m[best[b]].c)
                best[b]=i;
        }

        for(int i=1; i<=n; i++)
        {
            if(best[i]==-1)continue;

            int id=best[i];

            int a=m[id].a;
            int b=m[id].b;
            int c=m[id].c;

            if(rad(a)!=rad(b))
            {
                unire(a,b);

                cost+=c;
                comp--;

                nr++;
                sola[nr]=a;
                solb[nr]=b;
            }
        }
    }

    cout<<cost<<'\n'<<nr<<'\n';

        for(int i=1; i<=nr; i++)
            cout<<sola[i]<<' '<<solb[i]<<'\n';
}