#include <bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,nr,sum;
const int N=100001;
vector < pair < int , int > > apm;
vector < pair < int , pair < int , int > > >kr;
int cc[N];
vector < int > comp[N];
int viz[N];
void kruskal()
{
    for(auto i:kr)
    {
        if(apm.size()==n-1)
            return ;
        int ct=i.fr,x=i.sc.fr,y=i.sc.sc;
        if(cc[x]!=cc[y])
        {
            sum+=ct;
            apm.push_back({x,y});
            int cx=cc[x],cy=cc[y];
            for(int i:comp[cy])
            {
                comp[cx].push_back(i);
                cc[i]=cx;
            }
        }
    }
}
int main()
{
    int x,y,c,i;
    f>>n>>m;
    for(i=1; i<=m; ++i)
    {
        f>>x>>y>>c;
        kr.push_back({c,{x,y}});
    }
    sort(kr.begin(),kr.end());
    for(int i=1;i<=n;i++)
        cc[i]=i,comp[i].push_back(i);
        kruskal();
    g<<sum<<"\n"<<n-1<<"\n";
    for(auto i:apm)
        g<<i.fr<<" "<<i.sc<<"\n";
    return 0;
}