#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];
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 val=cc[y];
            for(int i=1;i<=n;++i)
                if(cc[i]==val)
                cc[i]=cc[x];
        }
    }
}
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;
        kruskal();
    g<<sum<<"\n"<<n-1<<"\n";
    for(auto i:apm)
        g<<i.fr<<" "<<i.sc<<"\n";
    return 0;
}