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

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

const int nMax=200002;
const int mMax=400002;
const int inf=1002; // costul e <=1000

int n,m, totalCost, costMin[nMax], parent[nMax];
vector<pair<int,int>> graph[nMax], apm;
bool inApm[nMax];

void prim(int start)
{
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    costMin[start]=0;
    pq.push({0,start});

    while(!pq.empty())
    {
        int cost= pq.top().first;
        int node=pq.top().second;
        pq.pop();

        if(inApm[node])
            continue;

        inApm[node]=true;
        totalCost+=cost;

        if(parent[node]!=-1)
            apm.push_back({parent[node],node});

        for(auto [adj,costEdge]:graph[node])
        {
            if(!inApm[adj] && costEdge < costMin[adj])
            {
                costMin[adj]=costEdge;
                parent[adj]=node;
                pq.push({costMin[adj], adj});
            }
        }
    }

}









int main()
{   
    fin>>n>>m;

    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }

    for(int i=1; i<=n; i++)
    {
        costMin[i]=inf;
        parent[i]=-1;
        inApm[i]=false;
    }

    prim(1);
    fout<<totalCost<<"\n";
    fout<<apm.size()<<"\n";
    for(auto [a,b]:apm)
        fout<<a<<" "<<b<<"\n";

    return 0;
}