#include <fstream>
#include <vector>
#define inf 0x3f3f3f3f
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,i,x,y,z,nr,c,sel[200005],sol,poz,cost;
vector <pair<int,int> > v[200005];
pair<int,int> dp[200005],ras[200005];
int main()
{
    in>>n>>m;
    for (i=1;i<=m;++i)
    {
        in>>x>>y>>c;
        v[x].push_back({y,c});
        v[y].push_back({x,c});
    }
    sel[1]=1;
    for (i=2;i<=n;++i)
        dp[i].first=inf;
    for (i=0;i<v[1].size();++i)
    {
        dp[v[1][i].first].first=v[1][i].second;
        dp[v[1][i].first].second=1;
    }
    for (nr=2;nr<=n;++nr)
    {
        sol=inf;
        for (i=1;i<=n;++i)
        {
            if (sel[i]==0) {if (dp[i].first<sol) {sol=dp[i].first; poz=i;}}
        }
        sel[poz]=1;
        cost+=sol;
        ras[nr-1]={poz,dp[poz].second};
        for (i=0;i<v[poz].size();++i)
        if (v[poz][i].second<dp[v[poz][i].first].first) {dp[v[poz][i].first].first=v[poz][i].second; dp[v[poz][i].first].second=poz;}
    }
    out<<cost<<'\n';
    out<<n-1<<'\n';
    for (i=1;i<=n-1;++i)
    {
        out<<ras[i].first<<" "<<ras[i].second<<'\n';
    }
    return 0;
}