#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);

int n,m;
int parent[NMAX];
int dist[NMAX], totCost;
int visited[NMAX];
vector<pair<int,int> > graph[NMAX];

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

    while(true)
    {
        int minim=INF;
        int poz=0;
        for(int i=1;i<=n;++i)
        {
            if(dist[i]<minim&&!visited[i])
            {
                minim=dist[i];
                poz=i;
            }
        }
        if(minim!=INF)
        {
            visited[poz]=1;
            for(int i=0;i<graph[poz].size();++i)
            {
                int ind=graph[poz][i].first;
                int c=graph[poz][i].second;
                if(dist[ind]>c&&!visited[ind])
                {
                    dist[ind]=c;
                    parent[ind]=poz;
                }
            }
        }
        else break;
    }

    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;
}