#include <bits/stdc++.h>
//#define in cin
//#define out cout

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

const int nmax = 2e5+7;

struct DSU
{
    struct DSUnode
    {
        int p,s;
        DSUnode()
        {
            p=0;
            s=1;
        }
    }nodes[nmax];
    int getP(int ind)
    {
        if(nodes[ind].p==0)return ind;
        return nodes[ind].p=getP(nodes[ind].p);
    }
    bool sameTree(int a,int b)
    {
        return getP(a)==getP(b);
    }
    void unite(int a,int b)
    {
        int pa=getP(a);
        int pb=getP(b);
        if(nodes[pa].s>nodes[pb].s)
        {
            swap(pa,pb);
        }
        nodes[pa].p=pb;
        nodes[pb].s+=nodes[pa].s; 
    }
}dsu;

int n,m;
vector<pair<int,int>> adj[nmax];
vector<int> mst[nmax];
int colors[nmax];
vector<vector<int>> colorGroups;
vector<pair<int,int>> ress;

struct edge
{
    int a,b,c;
    edge(int a,int b,int c=INT_MAX):a(a),b(b),c(c)
    {

    }
    bool operator<(const edge &other)const
    {
        return c<other.c;
    }
};

void dfs(int ind,int color,vector<int> &v)
{
    if(colors[ind])return;
    colors[ind]=color;
    v.push_back(ind);
    for(auto i:mst[ind])
    {
        dfs(i,color,v);
    }
}

void printColors()
{
    for(int i=1;i<=n;i++)
    {
        cerr<<i<<' '<<colors[i]<<'\n';
    }
    cerr<<'\n';
    for(auto i:colorGroups)
    {
        for(auto j:i)cerr<<j<<' ';
        cerr<<'\n';
    }
    cerr<<'\n';
}

int main()
{
    in>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        in>>a>>b>>c;
        adj[a].push_back({c,b});
        adj[b].push_back({c,a});
    }

    int res=0;

    for(int it=0;it<40;it++)
    {
        for(int i=1;i<=n;i++)colors[i]=0;
        int colorcnt=0;
        colorGroups.clear();
        for(int i=1;i<=n;i++)
        {
            if(!colors[i])
            {
                colorcnt++;
                vector<int> tmp;
                dfs(i,colorcnt,tmp);
                colorGroups.push_back(tmp);
            }
        }
        //cerr<<'\n';
        //printColors();
        if(colorcnt==1)break;
        for(auto i:colorGroups)
        {
            edge muchie = edge(0,0);
            for(auto j:i)
            {
                for(auto k:adj[j])
                {
                    if(colors[k.second]!=colors[j])
                    {
                        //cerr<<j<<' '<<k.second<<'\n';
                        muchie=min(muchie,edge(j,k.second,k.first));
                    }
                }
            }
            if(muchie.b!=0&&!dsu.sameTree(i[0],muchie.b))
            {
                //cerr<<"alaa "<<muchie.a<<' '<<muchie.b<<'\n';
                dsu.unite(muchie.a,muchie.b);
                mst[muchie.a].push_back(muchie.b);
                mst[muchie.b].push_back(muchie.a);
                res+=muchie.c;
                ress.push_back({muchie.a,muchie.b});
            }
        }
    }
    out<<res<<'\n';
    out<<n-1<<'\n';
    for(auto i:ress)
    {
        out<<i.first<<' '<<i.second<<'\n';
    }
}