#include<cstdio>
#include<vector>
#include<queue>
#define _NMAX 200010
#define _MMAX 400010
using namespace std;

int nN, nM;
struct muchie_part
{
    int dest, cost;
};

vector<muchie_part > lAd[_NMAX];
int parent[_NMAX];

int tree_cost;
void tree();
int main()
{
    FILE *f=fopen("apm.in", "r");
    fscanf(f, "%d %d", &nN, &nM);
    for (int i=1;i<=nM;i++)
    {
        int nod1, nod2;
        muchie_part tmp;
        fscanf(f,"%d %d %d", &nod1, &nod2, &tmp.cost);
        tmp.dest=nod2; lAd[nod1].push_back(tmp);
        tmp.dest=nod1; lAd[nod2].push_back(tmp);
    }
    tree();
    f=fopen("apm.out", "w");
    fprintf(f,"%d\n%d\n", tree_cost, nN-1);
    for (int i=2;i<=nN;i++)
        fprintf(f,"%d %d\n", i, parent[i]);
    return 0;
}

struct muchie
{
    int x,y,cost;
};

struct cost_bigger
{
    bool operator()(muchie a, muchie b)
    {
        return a.cost>b.cost;
    };
};

//tree_dist;
bool treed[_NMAX];
void push_m_ad(priority_queue<muchie, vector<muchie >, cost_bigger> &q, int nod)
{
    for (int i=0;i<lAd[nod].size();i++)
    {
        int dest=lAd[nod].at(i).dest;
        if (treed[dest]) continue; //GLOBAL
        muchie tmp;
        tmp.x=nod; tmp.y=dest; tmp.cost=lAd[nod].at(i).cost;
        q.push(tmp);
    }
}
void tree()
{
    priority_queue<muchie, vector<muchie >, cost_bigger> q;
    push_m_ad(q,1); treed[1]=1;
    while (!q.empty())
    {
        muchie cur;
        cur=q.top(); q.pop();
        if (treed[cur.y]) continue;
        parent[cur.y]=cur.x; tree_cost+=cur.cost;
        push_m_ad(q,cur.y); treed[cur.y]=1;
    }

    treed[1]=1;
}