#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <fstream>




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


int main()
{
    int m,n;
    fin>>n>>m;
    vector<vector<pair<int,int>>> adj(n+1);
    unordered_map<int,bool> visited;
    vector<int> parent(n+1);
    int total = 0;
    
    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;
    for(int i=0;i<m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        adj[x].push_back(make_pair(y,c));
        adj[y].push_back(make_pair(x,c));
    }
    int start = 1;
    parent[start] = start;
    visited[start] = true;
    for(auto edge: adj[start])
    {
        pq.push(make_pair(edge.second, make_pair(start, edge.first)));
    }
    int novisited = 1;
    while (novisited < n) {
    auto currEdge = pq.top();
    pq.pop();

    int cost = currEdge.first;
    int from = currEdge.second.first;
    int to   = currEdge.second.second;

    if (visited[to]) continue;

    visited[to] = true;
    novisited++;
    total += cost;
    parent[to] = from;

        
      for (auto &edge : adj[to])
         if (!visited.count(edge.first))
            pq.push({edge.second, {to, edge.first}});

    }


    fout<<total<<endl;
    fout<<n-1<<endl;
    for(int i=2;i<=n;i++)
    {
        fout<<parent[i]<<" "<<i<<endl;
    }





    return 0;


}