#include <fstream>
#include <vector>
#define nMax 200005
#define pb push_back
#define mkp make_pair
#define INF 1 << 30
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<pair<int, int> > G[nMax], Edge;
int n, m, Sol, k, poz[nMax], heap[nMax], vec[nMax], val[nMax];
void in_apm(int node)
{
    for(vector<pair<int, int> >::iterator it=G[node].begin();it!=G[node].end();it++)
    {
        int fiu=it->first;
        int cost=it->second;
        val[fiu]=min(val[fiu], cost);
        if(val[fiu]==cost)
            vec[fiu]=node;
    }
}
void read()
{
    int a, b, c;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        G[a].pb(mkp(b, c));
        G[b].pb(mkp(a, c));
    }
}
void upDate(int pozi)
{
    int po;
    while(pozi/2>0)
    {
        po=pozi/2;
        if(val[heap[po]]>val[heap[pozi]])
        {
            swap(poz[heap[po]], poz[heap[pozi]]);
            swap(heap[po], heap[pozi]);
            pozi=po;
        }
        else
            break;
    }
}
void downDate(int pozi)
{
    int po;
    while(pozi*2<=k)
    {
        po=pozi*2;
        if(po+1<=k && val[heap[po+1]]<val[heap[po]])
            po++;
        if(val[heap[pozi]]>val[heap[po]])
        {
            swap(poz[heap[pozi]], poz[heap[po]]);
            swap(heap[po], heap[pozi]);
            pozi=po;
        }
        else
            break;
    }
}
int in_heap(int node)
{
    heap[++k]=node;
    poz[node]=k;
    upDate(k);
}
int out_heap()
{
    int node=heap[1];
    swap(poz[heap[1]], poz[heap[k]]);
    swap(heap[1], heap[k--]);
    downDate(1);
    poz[node]=0;
    return node;
}
void solve()
{
    for(int i=2;i<=n;i++)
        val[i]=INF;
    in_apm(1);
    for(int i=2;i<=n;i++)
        in_heap(i);
    for(int i=2;i<=n;i++)
    {
        int node=out_heap();
        in_apm(node);
        Sol+=val[node];
        Edge.pb(mkp(node, vec[node]));
        for(vector<pair<int, int> >::iterator it=G[node].begin();it!=G[node].end();it++)
        {
            int fiu=it->first;
            if(poz[fiu])
                upDate(poz[fiu]);
        }
    }
}
void write()
{
    fout<<Sol<<'\n'<<Edge.size()<<'\n';
    for(vector<pair<int, int> >::iterator it=Edge.begin();it!=Edge.end();it++)
        fout<<it->first<<" "<<it->second<<'\n';
}
int main()
{
    read();
    solve();
    write();
}