#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin("apm.in");
ofstream fout("apm.out");
 
const int NMax=200005;
const int oo=(1 << 30);
 
int N,M;
int S,nr,rasp[NMax];
bool visit[NMax];
int Cost[NMax];
 
vector <pair <int,int> >a[NMax];
 
struct comp
{
    bool operator()(int a, int b)
    {
        return Cost[a]>Cost[b];
    }
};
 
priority_queue <int, vector<int>, comp> coada;
priority_queue <int, vector<int>, comp> coada1;
 
void Afiseaza(priority_queue <int, vector<int>, comp> a1)
{
	while(!a1.empty())
	{
		cout << a1.top() << " ";
		a1.pop();
	}
	cout << endl;
}
void Citeste()
{
    fin >> N >> M;
    for(int i=1;i<=M;i++)
    {
        int x,y,c;
        fin >> x >> y >> c;
        a[x].push_back(make_pair(y,c));
        a[y].push_back(make_pair(x,c));
    }
    for(int i=1;i<=N;i++)
        Cost[i]=oo;
}
void Prim(int st)
{
    visit[st]=true;
    coada.push(st);
    Cost[st]=0;
    while(!coada.empty())
    {
        int Nod=coada.top();
        coada.pop();
        visit[Nod]=true;
        nr++;
        rasp[nr]=Nod;
        S+=Cost[Nod];
        bool ok=false;
        for(int i=0;i<a[Nod].size();i++)
        {
            int Vecin=a[Nod][i].first;
            int C=a[Nod][i].second;
            if(C<Cost[Vecin])
            {
            	if(Cost[Vecin]!=oo and visit[Vecin]==true and Vecin!=1)
            	    ok=true;
            	Cost[Vecin]=C;
			}
            if(visit[Vecin]==false)
            {
                coada.push(Vecin);
                visit[Vecin]=true;
            }
        }
        if(ok)
        {
        	while(!coada.empty())
                coada1.push(coada.top()), coada.pop();
            while(!coada1.empty())
                coada.push(coada1.top()), coada1.pop();
		}
    }
}
int main()
{
     
    Citeste();
    Prim(1);
     
    fout << S << endl << N-1 << endl;
     
    for(int i=1;i<nr;i++)
        fout << rasp[i] << " " << rasp[i+1] << endl;
     
    return 0;
     
}