#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int nmax=2e5, mmax=4e5;
int parent[nmax+1], status[mmax+1];
int n, m;
struct drum
{
    int x, y, c;
}d[mmax+1];
bool cmp(drum a, drum b)
{
    return (a.c<b.c);
}
int findRoot(int nod)
{
    if(parent[nod]==nod)
        return nod;
    return parent[nod]=findRoot(parent[nod]);
}
void setUnion(int nod1, int nod2)
{
    nod1=findRoot(nod1);
    nod2=findRoot(nod2);
    if(nod1==nod2)
    {
        return ;
    }
    if(status[nod1]<status[nod2])
    {
        swap(nod1, nod2);
    }
    if(status[nod1]==status[nod2])
        status[nod1]++;
    parent[nod2]=nod1;
}
vector <int> sol;
int main()
{
    in>>n>>m;
    for(int i=1; i<=n; i++)
    {
        parent[i]=i;
        status[i]=1;
    }
    for(int i=1; i<=m; i++)
    {
        in>>d[i].x>>d[i].y>>d[i].c;
    }
    sort(d+1, d+m+1, cmp);
    int rez=0;
    //queue <pair<int, int>> q;
    for(int i=1; i<=m; i++)
    {
        if(findRoot(d[i].x)!=findRoot(d[i].y))
        {
            rez+=d[i].c;
            sol.push_back(i);
            setUnion(d[i].x, d[i].y);
        }
    }
    out<<rez<<'\n'<<n-1<<'\n';
    for(int it:sol)
    {
        out<<d[it].x<<" "<<d[it].y<<'\n';
    }
}