#include <bits/stdc++.h>
using namespace std;
string const filename="apm";
ifstream fin (filename+".in");
ofstream fout (filename+".out");
int const lmax=200007;
int const vmax=1007;
int const mmax=2*lmax;
int t[lmax],dist[lmax],n,m,ind=0;
int update_node[lmax];
bool viz[lmax];
struct graf{
int node, cost;
};
pair<int,int>muchie[mmax];
vector <graf> G[lmax];
int cost_final=0;
void prim(int start_node)
{
    dist[start_node]=-1;
    viz[start_node]=true;
    for(auto vec:G[start_node])
    {
        if(dist[vec.node]>vec.cost)
        {
            dist[vec.node]=vec.cost;
            update_node[vec.node]=start_node;
        }
    }
    for(int i=0;i<n-1;i++)
    {
        int minim=vmax;
        int best=-1;
        for(int j=1;j<=n;j++)
        {
            if(viz[j]==true)continue;
            if(minim>dist[j])
            {
                minim=dist[j];
                best=j;
            }
        }
        cost_final+=dist[best];
        t[best]=update_node[best];
        muchie[ind].first=best;
        muchie[ind].second=update_node[best];
        ind++;
        viz[best]=true;///il adaug pe best in componenta, tatal sau este cel care a relaxat ultima data distanta sa
        for(auto vec:G[best])
        {
            if(viz[vec.node]==false and dist[vec.node]>vec.cost)
            {
                dist[vec.node]=vec.cost;
                update_node[vec.node]=best;

            }
        }

    }

}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        dist[i]=vmax;
    }
    for(int i=0;i<m;i++)
    {
        int a,b,h;
        fin>>a>>b>>h;
        G[a].push_back({b,h});
        G[b].push_back({a,h});
    }
    prim(1);
    fout<<cost_final<<"\n"<<n-1<<"\n";
    for(int i=0;i<ind;i++)
    {
        fout<<muchie[i].first<<" "<<muchie[i].second<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}