#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>

#define ff first
#define ss second
#define tat (x >> 1)
#define fiu1 (x << 1)
#define fiu2 (fiu1 + 1)

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

typedef pair <int, int> nod;
const int Nmax = 200010;
const int oo = 0x3f3f3f3f;

int N, M, lg, sol, v[Nmax], poz[Nmax], h[Nmax], vec[Nmax];
vector <nod> a[Nmax];
vector <nod> s;

void Add_APM(int x)
{
    for(unsigned i=0; i<a[x].size(); i++)
    {
        int newn = a[x][i].ff, cost = a[x][i].ss;
        v[newn] = min(v[newn], cost);
        if(v[newn] == cost) vec[newn] = x;
    }
}

void Push(int x)
{
    while(tat && v[h[x]] < v[h[tat]])
    {
        swap(h[x], h[tat]);
        swap(poz[h[x]], poz[h[tat]]);
        x = tat;
    }
}

void Add_Heap(int x)
{
    h[++lg] = x;
    poz[x] = lg;
    Push(lg);
}

void Pop(int x)
{
    int y;
    while(x != y)
    {
        y = x;
        if(fiu1 <= lg && v[h[x]] > v[h[fiu1]]) x = fiu1;
        if(fiu2 <= lg && v[h[x]] > v[h[fiu2]]) x = fiu2;

        swap(h[x], h[y]);
        poz[h[x]] = x;
        poz[h[y]] = y;
    }
}

int Min_Heap()
{
    int nod = h[1];
    int cop = v[nod];
    v[nod] = -1;
    Push(poz[nod]);
    v[nod] = cop;

    poz[h[1]] = 0;
    h[1] = h[lg--];
    poz[h[1]] = 1;

    Pop(1);
    return nod;
}

int main()
{
    fin>>N>>M;
    for(int i=1; i<=M; i++)
    {
        int x, y, c;
        fin>>x>>y>>c;
        a[x].push_back(nod(y, c));
        a[y].push_back(nod(x, c));
    }
    for(int i=1; i<=N; i++)
        v[i] = oo; v[1] = 0;
    Add_APM(1);

    for(int i=2; i<=N; i++)
        Add_Heap(i);

    for(int i=1; i<N; i++)
    {
        int x = Min_Heap();
        Add_APM(x);
        sol += v[x];
        s.push_back(nod(x, vec[x]));
        for(unsigned j=0; j<a[x].size(); j++)
            if(poz[a[x][j].ff])
                Push(poz[a[x][j].ff]);
    }
    fout<<sol<<'\n'<<N-1<<'\n';
    for(unsigned i=0; i<s.size(); i++)
        fout<<s[i].ff<<' '<<s[i].ss<<'\n';
    return 0;
}