#include <fstream>
#include <vector>
#include <limits.h>

#define nMax 200001
#define pb push_back
#define mkp make_pair
#define INF INT_MAX
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, apmCost, k;
int heap[nMax], poz[nMax], dist[nMax], Vec[nMax];
vector<pair<int, int> > G[nMax], Edge;
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)
    {
        po=pozi/2;
        if(dist[heap[po]]>dist[heap[pozi]])
        {
            swap(heap[po], heap[pozi]);
            swap(poz[heap[po]], poz[heap[pozi]]);
            pozi=po;
        }
        else
            break;
    }
}
void downDate(int pozi)
{
    int po;
    while(pozi*2<=k)
    {
        po=pozi*2;
        if(po+1<=k && dist[heap[po]]>dist[heap[po+1]])
            po++;
        if(dist[heap[po]]<dist[heap[pozi]])
        {
            swap(heap[po], heap[pozi]);
            swap(poz[heap[po]], poz[heap[pozi]]);
            pozi=po;
        }
        else
            break;
    }
}
void insert_apm(int node)
{
    for(vector<pair<int, int> >::iterator it=G[node].begin();it!=G[node].end();it++)
    {
        int fiu=it->first;
        int dst=it->second;

        if(dist[fiu]>dst)
        {
            dist[fiu]=dst;
            Vec[fiu]=node;
        }
    }
}
void insert_heap(int node)
{
    heap[++k]=node;
    poz[node]=k;
    upDate(k);
}
int extract_heap(int pozi)
{
    int node=heap[pozi];
    swap(heap[pozi], heap[k]);
    swap(poz[heap[pozi]], poz[heap[k]]);
    poz[heap[k]]=0;
    k--;
    downDate(pozi);

    return node;
}
void solve()
{
    for(int i=2;i<=n;i++)
        dist[i]=INF;

    insert_apm(1);
    for(int i=2;i<=n;i++)
        insert_heap(i);

    while(k)
    {
        int node=extract_heap(1);
        insert_apm(node);
        apmCost+=dist[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<<apmCost<<'\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();
    return 0;
}