#include <bits/stdc++.h>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
int const lmax=200007;
int n,m;
int t[lmax],h[lmax];
struct muchie
{
    int x;
    int y;
    long long int cost;
};
bool cmp(muchie a, muchie b)
{
    return a.cost<b.cost;
}
muchie v[lmax*2];
int root(int node)
{
    if(t[node]==0)
    {
        return node;
    }
    int aux=root(t[node]);
    t[node]=aux;
    return aux;
}
void merger(int node1, int node2)
{
    int r1=root(node1);
    int r2=root(node2);
    if(r1==r2)return;
    if(h[r1]==h[r2])
    {
        t[r1]=r2;
        h[r2]++;
    }
    else if(h[r1]<h[r2])
    {
        t[r1]=r2;
    }
    else
    {
        t[r2]=r1;
    }
}
long long int apmcost=0;
muchie sol[lmax*2];
int hh=0;
void Kruskal()
{
    for(int i=0;i<m;i++)
    {
        int n1=v[i].x;
        int n2=v[i].y;
        long long int cost=v[i].cost;
        int r1=root(n1);
        int r2=root(n2);
        if(r1==r2)continue;
        merger(n1,n2);
        sol[hh].x=n1;
        sol[hh].y=n2;
        sol[hh].cost=cost;
        hh++;
        apmcost+=cost;
    }
    fout<<apmcost<<"\n"<<n-1<<"\n";
    for(int i=0;i<n-1;i++)
    {
        fout<<sol[i].x<<" "<<sol[i].y<<"\n";
    }
}
int main()
{
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        long long int c;
        fin>>a>>b>>c;
        v[i].x=a;
        v[i].y=b;
        v[i].cost=c;
    }
    sort(v,v+m,cmp);
    Kruskal();
    fin.close();
    fout.close();
    return 0;
}