#include <bits/stdc++.h>

using namespace std;

vector <int> par;
vector <int> sz;

void initialize (int n)
{
	par.resize(n+1);
	sz.resize(n+1 , 1);
	for (int i = 1; i <= n; i++)
	{
		par[i] = i;
	}
}

int Find (int nod)
{
	if (par[nod] == nod) return nod;
	else return par[nod] = Find(par[nod]);
}

void unite (int x , int y)
{
	int repX = Find(x) , repY = Find(y);
    //if (s[repX] < s[repY]) swap(repX , repY);
	if (repX != repY)
    {
	if(sz[repX] > sz[repY])
		par[repY]=repX, sz[repX]+=sz[repY];
    else
        par[repX]=repY, sz[repY]+=sz[repX];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int n, m, a, b, c;
    cin>>n>>m;
    initialize(n);
    pair<int, pair<int, int>> v[m+1]; ///<cost, <st, dr>>
    for(int i=1; i<=m; i++)
    {
        cin>>a>>b>>c;
        v[i].first=c;
        v[i].second.first=a;
        v[i].second.second=b;
    }
    sort(v+1, v+m+1);///dupa cost
    int luate=0; ///maxim = n-1 (are toate nodurile)
    int unde=1;
    long long total=0;
    pair<int, int> sol[n];
    while(luate<n-1)
    {
        int st=v[unde].second.first;
        int dr=v[unde].second.second;
        int cost=v[unde].first;
        if(Find(st) != Find(dr))
        {
            unite(st, dr);
            luate++;
            sol[luate].first=st;
            sol[luate].second=dr;
            total+=cost;
        }
        ++unde;
    }
    cout<<total<<'\n'<<n-1<<'\n';
    for(int i=1; i<n; i++)
        cout<<sol[i].first<<' '<<sol[i].second<<'\n';
    return 0;
}