#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#include <utility>

using namespace std;

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

int cc, zz;
const int MAX = 1e4 + 5;
typedef pair<long long int, int> PII;
bool marked[MAX];
vector <PII> adj[MAX];
pair <int , int> z[MAX];
long long prim(int x)
{
    priority_queue<PII, vector<PII>, greater<PII> > Q;
    int y,ret;
    long long minimumCost = 0;
    PII p;
    Q.push(make_pair(0, x));
    while(!Q.empty())
    {
        // Select the edge with minimum weight
        p = Q.top();
        Q.pop();
        int zx = p.second;
        // Checking for cycle
        if(marked[zx] == true)
            continue;
        minimumCost += p.first;
        marked[zx] = true;
        for(int i = 0;i < adj[zx].size();++i)
        {
            if (p.first == adj[zx][i].first)
                z[++cc] = make_pair(zx, adj[zx][i].second);
            y = adj[zx][i].second;
            if(marked[y] == false)
            {
                Q.push(adj[zx][i]);
                //z[++cc].first=x;
                //z[cc].second=y;
            }
        }
    }
    return minimumCost;
}

int main()
{
    int nodes, edges, x, y;
    long long weight, minimumCost;
    fin >> nodes >> edges;
    for(int i = 0;i < edges;++i)
    {
        fin >> x >> y >> weight;
        adj[x].push_back(make_pair(weight, y));
        adj[y].push_back(make_pair(weight, x));
    }
    // Selecting 1 as the starting node
    minimumCost = prim(1);
    fout << minimumCost <<endl << cc<<endl;
    for (int i = 1; i <= cc; ++i)
        fout << z[i].first << ' ' << z[i].second << "\n";
    return 0;
}