#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
typedef long long ll;
typedef pair<int,int> pi;
int t,T;
int n,m;
const int dim=2e5+10;

vector < pi > V[dim];
vector < int > h(dim),ft(dim);

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

vector < edge > E,rez;

void Union(int x,int y)
{
    if(h[x]<h[y]) ft[x]=y; //arborele cu rad x are mai putine niv decat arborele cu rad y
    else
    {
        if(h[x]==h[y]) h[x]++;
        ft[y]=x;
    }
}

int Find(int x)
{
    int root=x;
    while(ft[root]!=-1)
        root=ft[root];

    int aux=x;
    while(x!=root)
    {
        aux=ft[x];
        ft[x]=root;
        x=aux;
    }
    return root;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        V[a].pb({b,c});
        V[b].pb({a,c});

        E.pb({a,b,c});

    }
    for(int i=1;i<=n;i++)
    {
        h[i]=0;
        ft[i]=-1;
    }

    sort(E.begin(),E.end(),[&](edge X,edge Y){
         if(X.c==Y.c)
            return X.a<Y.a;
         return (X.c<Y.c);

         });
    int ans=0;
    for(int i=0;i<E.size();i++)
    {
        int u=E[i].a;
        int v=E[i].b;
        int cost=E[i].c;

        int find_u=Find(u),find_v=Find(v);

        if(find_u!=find_v)
        {
            ans+=cost;
            rez.pb({u,v,cost});
            Union(find_u,find_v);
        }
    }

    g<<ans<<'\n';
    g<<n-1<<'\n';
    for(edge X:rez) g<<X.a<<' '<<X.b<<'\n';

    return 0;
}