#include <cstdio>
#include <vector>
#include <fstream>

#define nMax 200001
#define buffMax 1001
#define INF 2000000000
#define pb push_back
#define mkp make_pair
#define x first
#define y second

using namespace std;

int n, m, Sol, poz1, nrHeap;
int poz[nMax], heap[nMax], Vec[nMax], dist[nMax];
vector<pair<int, int> > G[nMax], solEdges;
char buff[buffMax];

void read(int &nr)
{
    nr=0;
    int rev=0;
    while(buff[poz1]<'0' || buff[poz1]>'9')
    {
        if(buff[poz1]=='-')
            rev=1;
        poz1++;
        if(poz1==buffMax)
        {
            poz1=0;
            fread(buff, 1, buffMax, stdin);
        }
    }

    while(buff[poz1]>='0' && buff[poz1]<='9')
    {
        nr=nr*10+buff[poz1]-'0';
        poz1++;
        if(poz1==buffMax)
        {
            poz1=0;
            fread(buff, 1, buffMax, stdin);
        }
    }

    if(rev)
        nr=-nr;
}

void insertApm(int node)
{
    for(vector<pair<int, int> >::iterator it=G[node].begin(); it!=G[node].end(); it++)
    {
        int vec=it->first, cost=it->second;
        dist[vec]=min(dist[vec], cost);
        if(dist[vec]==cost)
            Vec[vec]=node;
    }
}

void upDate(int pozi)
{
    int po;
    while(pozi/2)
    {
        po=pozi/2;
        if(dist[heap[pozi]]<dist[heap[po]])
        {
            swap(heap[pozi], heap[po]);
            swap(poz[heap[pozi]], poz[heap[po]]);
            pozi=po;
        }
        else
            break;
    }
}

void downDate(int pozi)
{
    int po;
    while(2*pozi<=nrHeap)
    {
        po=2*pozi;
        if(po+1<=nrHeap && dist[heap[po]]>dist[heap[po+1]])
            po++;
        if(dist[heap[pozi]]>dist[heap[po]])
        {
            swap(heap[pozi], heap[po]);
            swap(poz[heap[pozi]], poz[heap[po]]);
            pozi=po;
        }
        else
            break;
    }
}

void insertHeap(int node)
{
    heap[++nrHeap]=node;
    poz[node]=nrHeap;
    upDate(nrHeap);
}

int extractHeap(int pozi)
{
    int node=heap[pozi];
    swap(heap[pozi], heap[nrHeap]);
    swap(poz[heap[pozi]], poz[heap[nrHeap]]);
    nrHeap--;
    downDate(1);
    poz[node]=0;
    return node;
}

int main()
{
    int a, b, c;
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    fread(buff, 1, buffMax, stdin);
    read(n); read(m);

    for(int i=1; i<=m; i++)
    {
        read(a); read(b); read(c);
        G[a].pb(mkp(b, c));
        G[b].pb(mkp(a, c));
    }

    for(int i=1; i<=n; i++)
        dist[i]=INF;
    dist[1]=0; insertApm(1);
    for(int i=2; i<=n; i++)
        insertHeap(i);

    while(nrHeap)
    {
        int node=extractHeap(1);
        Sol+=dist[node];
        insertApm(node);
        solEdges.pb(mkp(node, Vec[node]));
        for(vector<pair<int, int> >::iterator it=G[node].begin(); it!=G[node].end(); it++)
        {
            int fiu=it->first, cost=it->second;
            if(poz[fiu])
                upDate(poz[fiu]);
        }
    }

    printf("%d\n%d\n", Sol, n-1);
    for(vector<pair<int, int> >::iterator it=solEdges.begin(); it!=solEdges.end(); it++)
        printf("%d %d\n", it->first, it->second);
}