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


using namespace std;

const int N=200001;
const int M=400001;
const int INF=1000000001;

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

priority_queue<pair <int,int>>h;
vector<pair <int,int>>a[N], arbore;
int d[N],n,m, cost, pred[N];
bool in_arb[N];

void prim()
{
    for (int i = 2; i <= n; i++)
    {
        d[i] = INF;
    }
    d[1] = 0;
    h.push({0,1});
    while (!h.empty())
    {
        int x = h.top().second;
        h.pop();
        if (in_arb[x])
            continue;
        if (pred[x])
            arbore.push_back({x,pred[x]});
        in_arb[x]=1;
        cost+=d[x];
        for (auto p:a[x])
        {
            int y=p.first;
            int c=p.second;
            if (!in_arb[y] && c<d[y])
            {
                d[y]=c;
                pred[y]=x;
                h.push({-c,y});
            }
        }
    }
}

int main()
{
    in>>n>>m;
    for (int i=1;i<=m;i++)
	{
	    int x, y, dist;
	    in>>x>>y>>dist;
	    a[x].push_back({y,dist});
	    a[y].push_back({x,dist});
	}
	prim();
	out<<cost<<"\n";
	out<<arbore.size()<<"\n";
	for (auto i:arbore)
    {
        out<<i.first<<" "<<i.second<<"\n";
    }
    return 0;
}