#include <bits/stdc++.h>
#define NMAX 1000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int conex[NMAX]; // in ce componenta se afla i
struct thg{ int x, y; double cost; };
int N,M;
vector<thg> much;
vector <int> sol[NMAX]; //arborele
bool comp(thg a, thg b)
{
    return (a.cost<b.cost);
}
void unificare(int x, int y)
{
    int reff = conex[y];
    for(int i=1;i<=N;++i)
        if(conex[i] == reff) conex[i]=conex[x];
}
int main()
{
    int x,y;
    double cost;
    fin>>N>>M;
    for(int i=1;i<=M;++i)
    {
        fin>>x>>y>>cost;
        much.push_back({x,y,cost});
    }
    for(int i=1;i<=N;++i)
        conex[i]=i;
    sort(much.begin(), much.end(), comp);
    int start=0, S=0;
    for(int i=1;i<=N-1;++i) //aleg cele N-1 muchii din arbore
    {
        int ok=1;
        while(ok)
        {
            ok=0;
            int nodx=much[start].x, nody=much[start].y, costxy=much[start].cost;
            if(conex[nodx] != conex[nody])
            {
                S+=costxy;
                unificare(nodx, nody);
                sol[nodx].push_back(nody);

            }
            else ok=1;
            start++;
        }
    }
    fout<<S<<"\n";
    fout<<N-1<<"\n";
    for(int i=1;i<=N;++i)
    {
        if(sol[i].size())
            for(auto z:sol[i])
                fout<<i<<" "<<z<<"\n";
    }
    return 0;
}