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

const int maxi=1<<30;

ifstream be("apm.in");
ofstream ki("apm.out");

void prim(vector<vector<pair<int,int> > >&adj ,int n)
{
    vector<bool>mstset(n+1,false);
    vector<int>parent(n+1,-1);
    vector<int>key(n+1,maxi);
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
    int src=1;
    int db=0;
    parent[src]=src;
    q.push({0,src});
    key[src]=0;
    while(!q.empty())
    {
        int u=q.top().second;
        int cost=q.top().first;
        q.pop();
        if(mstset[u] || cost!=key[u])continue;
        mstset[u]=true;
        db+=cost;
        for(auto p:adj[u])
        {
            int v=p.first;
            int c=p.second;
            if(mstset[v]==false && key[v]>c)
            {
                key[v]=c;
                q.push({key[v],v});
                parent[v]=u;
            }
        }
    }
    ki<<db<<endl<<n-1<<endl;
    for (int i = 1; i <= n; i++)
    {
        if(i!=src)
        {
            ki<<i<<" "<<parent[i]<<endl;
        }
    }

}


int main()
{
    int n,m;
    be>>n>>m;
    vector<vector<pair<int,int> > >adj(n+1);
    for(int i=0;i<m;i++)
    {
        int x,y,c;
        be>>x>>y>>c;
        adj[x].push_back({y,c});
        adj[y].push_back({x,c});
    }
    prim(adj,n);
    return 0;
}