#include <fstream>
#include <utility>
#include <vector>
#define NMAX 200005
#define INF 999999999

using namespace std;

FILE* f=freopen("apm.in","r",stdin);
FILE* o=freopen("apm.out","w",stdout);

typedef pair<int, int> pr;

int n,m;
vector<pr> graph[NMAX];
int parent[NMAX];
int dist[NMAX], totCost;
int visited[NMAX];
int poz[NMAX];
int heap[NMAX], heapSize;

void Swap(int a, int b)
{
    swap(poz[heap[a]],poz[heap[b]]);
    swap(heap[a],heap[b]);
}

void Insert(int x)
{
    heap[++heapSize]=x;
    int c=heapSize;
    int p=c/2;
    poz[x]=c;
    while(c>1&&dist[heap[p]]>dist[heap[c]])
    {
        Swap(p,c);
        c=p;
        p=c/2;
    }
}

void Shift(int p)
{
    int c=p*2;
    while(c<=heapSize)
    {
        if(c!=heapSize)
            if(dist[heap[c]]>dist[heap[c+1]])
                c+=1;
        if(dist[heap[p]]>dist[heap[c]])
        {
            Swap(p,c);
            p=c;
            c=p*2;
        }
        else break;
    }
}

int PopRoot()
{
    int root=heap[1];
    Swap(1,heapSize);
    poz[heap[heapSize--]]=0;
    Shift(1);
    return root;
}

void Prim(int x)
{
    for(int i=1;i<=n;++i)
    {
        parent[i]=x;
        dist[i]=INF;
    }

    parent[x]=dist[x]=0;
    Insert(x);
    while(heapSize)
    {
        int node=PopRoot();
        visited[node]=1;
        for(int i=0;i<graph[node].size();++i)
        {
            int ind=graph[node][i].first;
            int c=graph[node][i].second;
            if(dist[ind]>c&&!visited[ind])
            {
                if(dist[ind]==INF)
                {
                    dist[ind]=c;
                    Insert(ind);
                }
                else
                {
                    dist[ind]=c;
                    Shift(poz[ind]);
                }
                parent[ind]=node;
            }
        }
    }

    for(int i=1;i<=n;++i) totCost+=dist[i];
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        graph[x].push_back(make_pair(y,c));
        graph[y].push_back(make_pair(x,c));
    }

    Prim(1);

    printf("%d\n%d\n",totCost,n-1);
    for(int i=2;i<=n;++i)
        printf("%d %d\n",i,parent[i]);

    return 0;
}