#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

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

struct ceva{
    int nod, next, cost;
    friend bool operator < (ceva A, ceva B)
    {
        if(A.cost > B.cost)
            return true;
        else
            return false;
    }
    ceva() // constructor
    {
        nod = 0;
        cost = 0x3f3f3f3f;
        next = 0;
    }
    ceva(int x, int y, int z) // constructor
    {
        nod = x;
        next = y;
        cost = z;
    }
};

vector <vector <ceva> > G;
vector <int> tata, v;
int n, m;

int main()
{
    fin >> n >> m;
    G.resize(n+1);
    tata.resize(n+1, -1);
    v.resize(n+1, 0);

    int x, y, c;

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        G[x].push_back(ceva(x,y,c));
        G[y].push_back(ceva(y,x,c));
    }

    tata[1] = 0;
    v[1] = 1;
    priority_queue <ceva> Q;

    for(auto c : G[1])
        Q.push(c);

    int s = 0;
    while(!Q.empty())
    {
        auto top = Q.top();
        Q.pop();
        if(v[top.next] != 0) // vizitat
            continue;
        else
        {
            v[top.next] = 1;
            tata[top.next] = top.nod;
            s += top.cost;
            for(auto muchie : G[top.next])
                Q.push(muchie);
        }
    }

    fout << s  << '\n';
    fout << n - 1 << '\n';

    for(int i = 1; i <= n; i++)
        if(tata[i] != 0)
            fout << i << " " << tata[i] << '\n';

    fin.close();
    fout.close();
    return 0;
}